> #include<iostream>
> #include<string>
> using namespace std;
> #define M 105
> 
> int state[M][M]; //表示第i个括号到j个括号，配对之后的括号数
> string ans[M][M]; //表示第i个括号到j个括号，配对之后的符号串
> char str[M]; 
> int n;
> 
> bool Match(char x,char y)
> {
> 	if(x=='('&&y==')')
> 		return true;
> 	if(x=='['&&y==']')
> 		return true;
> 	return false;
> }
> 
> void Init()
> {
>      int i,j;
>      for(i=0;i<=n;i++)
> 		 for(j=0;j<=n;j++)
> 		 {
> 			 state[i][j]=0;
> 			 ans[i][j]="";
> 		 }
> 		 for(i=1;i<=n;i++)
> 		 {
> 			 state[i][i]=2;
> 			 if(str[i]=='('||str[i]==')')
> 				 ans[i][i]="()";
> 			 else
> 				 ans[i][i]="[]";     
> 		 }
> }
> int DP(int i,int j){
> 	int k;
> 	if(state[i][j])
> 		return state[i][j]; 
> 	int dist=99999;
> 	for(k=i;k<j;k++)
> 	{   
> 			if(dist>DP(i,k)+DP(k+1,j))
> 			{
> 				dist=DP(i,k)+DP(k+1,j);
> 				ans[i][j]=ans[i][k]+ans[k+1][j];
> 			}
> 			 if(Match(str[i],str[j]))
> 			 {
> 				 if(dist>DP(i+1,j-1)+2)
> 				 {
> 					 dist=state[i+1][j-1]+2;
> 					 ans[i][j]=str[i]+ans[i+1][j-1]+str[j];
> 				 }
> 			 }
> 	 } 
> 	state[i][j]=dist;
> 	return dist;     
> }
> int main()
> {
>     cin>>str+1;
>     n=strlen(str+1);
>     Init();
>     DP(1,n);
>     cout<<ans[1][n]<<endl;
>     return 0;
> }

• Re:我用纯dp过了，但是用备忘录却过不了，请高人看看程序 (13) ccsu2008021220 2009-09-22 21:57:47