posts - 100,  comments - 15,  trackbacks - 0
//黑书有介绍,参考,但要添加对相应串的存储,黑书的代码有可改进的...
#include<iostream>
#include
<string>
using namespace std;
#define INF 2000000000

char str[102];
int d[102][102];
string ans[102][102];

void dp()
{
    
int i,j,k,p,n;
    n
=strlen(str+1);
    
for(i=1;i<=n;i++
    
{
        d[i][i
-1]=0;
        d[i][i]
=1;
        
if(str[i]=='(') ans[i][i]="()";
        
if(str[i]==')') ans[i][i]="()";
        
if(str[i]=='[') ans[i][i]="[]";
        
if(str[i]==']') ans[i][i]="[]";
    }

    
for(p=1;p<n;p++)
    
{
        
for(i=1;i<=n-p;i++)
        
{
            j
=i+p;
            d[i][j]
=INF;
            
if(str[i]=='(' && str[j]==')')
            
{
                
if(d[i+1][j-1]<d[i][j])
                
{
                    d[i][j]
=d[i+1][j-1];
                    ans[i][j]
='('+ans[i+1][j-1]+')';
                }

            }

            
else {
                
if(str[i]=='[' && str[j]==']')
                
{
                    
if(d[i+1][j-1]<d[i][j])
                    
{
                        d[i][j]
=d[i+1][j-1];
                        ans[i][j]
='['+ans[i+1][j-1]+']';
                    }

                }

            }

            
for(k=i;k<=j-1;k++)
            
{
                
if(d[i][k]+d[k+1][j]<d[i][j])
                
{
                    d[i][j]
=d[i][k]+d[k+1][j];
                    ans[i][j]
=ans[i][k]+ans[k+1][j];
                }

            }

        }

    }

    cout
<<ans[1][n]<<endl;
}


int main()
{
    scanf(
"%s",str+1);
    dp();
    
return 0;
}

posted on 2009-05-19 01:00 wyiu 阅读(274) 评论(0)  编辑 收藏 引用 所属分类: POJ

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   博问   Chat2DB   管理