#include<stdio.h>
#include<string.h>
char a[105];
int dp[105][105],dp1[105][105];
int min(int a, int b, bool &f)
{
	if(a<b) 
	{
		f = true;
		return a;
	}
	else
	{
		f = false;
		return b;
	}
}
int justdo(int i, int j)
{
	bool f;
	int m=999999,k,zj;
    if(dp[i][j] >= 0) 
		return dp[i][j];
	if(i==j)
		return dp[i][j] = 1;
	if(j-i==1&&a[i]+a[j]==10 && a[j] > a[i])
	{
		 dp1[i][j] = 0;	 return dp[i][j] = 0;
	}
	else 
	{		
	   for(k=i; k<j;k++)
	   {
		 m = min(m, justdo(i,k)+justdo(k+1,j),f);
		 if(!f)
			 dp1[i][j] = k;
	   }
	   if(a[i]+a[j]==10 && a[j]>a[i])
	   {
		 m = min(m, justdo(i+1,j-1),f);
		 if(!f)
		 {
		   dp1[i][j] = 0;	
		 }
	   }
	   return dp[i][j] = m;
	}
	
}
void p(int i)
{
	if(i==1) printf("(");
	else if(i==9) printf(")");
	else if(i==2) printf("[");
	else printf("]");
}

void print(int i, int j)
{
	if(i==j)
	{
		if(a[i]>2)
		{
			p(10-a[i]);
			p(a[i]);
		}
		else
		{
			p(a[i]);
			p(10-a[i]);
		}
	}
	else if(!dp1[i][j])
	{		
		p(a[i]);
	  if(j-1>=i+1)
		 print(i+1,j-1);
		p(a[j]);
	}
	else 
	{
		print(i,dp1[i][j]);
		print(dp1[i][j]+1,j);
	}
}

int main()
{
	int l,i,j;
//	freopen("in.txt","r",stdin);
     scanf("%s",a+1);
	
		l= strlen(a+1);
   if(!l)
	   printf("\n");
   else{
		for(i=1;i<=l;i++)
		{
			if(a[i] == '(') a[i] = 1;
			else if(a[i] == ')') a[i] = 9;
			else if(a[i] == '[') a[i] = 2;
			else if(a[i] == ']') a[i] = 8;
		}
        for(i=1;i<=l;i++)
			for(j=i;j<=l;j++)
			{
				dp[i][j] = -1;
			}
		justdo(1,l);
		print(1,l);
		printf("\n");
   }
	
	return 0;
}

• Re:忘了处理空行WA了无数次，贴上代码，全部用的递归，打印也没保存，用的递归打印结果 (185) ld2rxt 2014-09-03 02:33:18