#include<iostream>
using namespace std;

#define MAXN 200
#define maxn 20000000

int sav[MAXN][MAXN]={0},adds[MAXN][MAXN]={0},dp[MAXN][MAXN]={0},slen;
char str[MAXN],s[MAXN];

void DP_solve()
{
	int i,j,k,step;
	for(i=0;i<slen;++i)
	{
		dp[i][i]=1;
		if('('==str[i])
			adds[i][i]=2;
		else if(')'==str[i])
			adds[i][i]=1;
		else if('['==str[i])
			adds[i][i]=4;
		else if(']'==str[i])
			adds[i][i]=3;
	}
	for(i=0;i<slen;++i)
		for(j=0;j<slen;++j)
			sav[i][j]=-1;
	for(step=0;step<slen;++step)
		for(i=0;i<slen-step;++i)
		{
			j=i+step;
			dp[i][j]=maxn;
			if((str[i]=='('&&str[j]==')')||(str[i]=='['&&str[j]==']'))
				if(dp[i][j]>dp[i+1][j-1]){
					dp[i][j]=dp[i+1][j-1];
					adds[i][j]=0;
				}
			if(str[i]=='(')
				if(dp[i][j]>dp[i+1][j]+1){
					dp[i][j]=dp[i+1][j]+1;
					adds[i][j]=1;
				}
			if(str[j]==')')
				if(dp[i][j]>dp[i][j-1]+1){
					dp[i][j]=dp[i][j-1]+1;
					adds[i][j]=2;
				}
			if(str[i]=='[')
				if(dp[i][j]>dp[i+1][j]+1){
					dp[i][j]=dp[i+1][j]+1;
					adds[i][j]=3;
				}
			if(str[i]==']')
				if(dp[i][j]>dp[i][j-1]+1){
					dp[i][j]=dp[i][j-1]+1;
					adds[i][j]=4;
				}		
			for(k=i;k<j;++k)
			{
				if(dp[i][j]>dp[i][k]+dp[k+1][j])
				{
					dp[i][j]=dp[i][k]+dp[k+1][j];
					sav[i][j]=k;
				}
			}
//			cout<<i<<":"<<j<<":"<<dp[i][j]<<":"<<sav[i][j]<<endl;
		}
}

void output(int i,int j)
{
//	cout<<i<<':'<<j<<endl;
	if(i>j)
		return;
	if(-1==sav[i][j]){
		if(0==adds[i][j]){
			if(str[i]!=' ')cout<<str[i];
			output(i+1,j-1);
			if(str[i]!=' ')cout<<str[j];
			return;
		}
		if(1==adds[i][j]){
			cout<<'(';
			output(i+1,j);
			cout<<')';
		}else if(2==adds[i][j]){
			cout<<'(';
			output(i,j-1);
			cout<<')';
		}else if(3==adds[i][j]){
			cout<<'[';
			output(i+1,j);
			cout<<']';
		}else if(4==adds[i][j]){
			cout<<'[';
			output(i,j-1);
			cout<<']';
		}
	}else{
		output(i,sav[i][j]);
		output(sav[i][j]+1,j);
	}
}

int main()
{
	scanf("%s",s);
	slen=0;
	for(int p=0;s[p]!='\0';++p)
		if(s[p]!=' ') str[slen++]=s[p];
	str[slen]='\0';
	//	cout<<str<<endl;
	if(str==""){
		cout<<endl;
	}
	DP_solve();
	output(0,slen-1);
	cout<<endl;
	return 0;
}

• Re:求测试数据 WHY WA----完全按照<黑书>DP (35) doee 2009-03-28 23:19:13
  • 谢谢大牛,我通过了所有数据还是WA...可能是SP的问题吧 (17) CydorniaKnight 2009-03-29 13:52:00
    • Re:谢谢大牛,我通过了所有数据还是WA...可能是SP的问题吧 (22) j_will 2009-04-27 15:14:08