题意:
把一串 括号变成合法的,输出其中一个合法解就好了。
状态:dp【i】【j】 表示 从i 到 j 的括号要加几个括号才变合法。负数和0都是不用加了。
状态转移方程:
dp【i】【j】=min(dp【i】【j】,dp【i】【k】+dp【k+1】【j】)
( 1<= k <=n , 0<=i<=n-k , j=i+k )
边界条件:
就是一个括号时dp值为1 ,即dp【i】【i】=1 ;
还有一个 判断条件 就是当dp【i】【j】 i 与 j 的括号匹配时 就要把它赋值为 -1;
递归输出就好了。。
/**最少的括号匹配数,及其输出其中一个合法答案。**/ #include <iostream> #include<cstdio> #include<cstring> using namespace std; const int MAXN=300; char br[MAXN]; int dp[MAXN][MAXN]; int pos[MAXN][MAXN]; int len;int ans; void out(int i,int j) { if(i>j) return ; if(i==j) { ans++; if(br[i]=='(' || br[i]==')') printf("()"); else printf("[]"); } else if(pos[i][j]==-1) { printf("%c",br[i]); out(i+1,j-1); printf("%c",br[j]); } else { out(i,pos[i][j]); out(pos[i][j]+1,j); } } int main() { int i,j,k,mid,t,T; scanf("%d",&T);getchar(); while(T--) { gets(br); len=strlen(br); memset(dp,0,sizeof(dp)); for(i=0;i<len;i++) dp[i][i]=1; for(k=1;k<len;k++) { for(i=0;i+k<len;i++) { j=i+k; dp[i][j]=0x7fffffff; if( (br[i]=='(' &&br[j]==')') || (br[i]=='[' &&br[j]==']') ) { dp[i][j] = dp[i+1][j-1] ;pos[i][j]=-1; } for(mid=i;mid<j;mid++) { if(dp[i][j] > (t=dp[i][mid]+dp[mid+1][j]) ) // 如果子问题有匹配更好的,t将比-1更小。 { dp[i][j] = t; pos[i][j]=mid; } } } } ans=0; out(0,len-1); printf("\n%d\n",ans); // printf("\n"); } return 0; }