根据路径打印符号，但目前的问题是，我区间dp都写不好
#include <iostream> #include <cstring> #include <cstdio> #include <algorithm> using namespace std; const int maxn=110; int dp[maxn][maxn]; char a[maxn]; const int inf=0x3f3f3f3f; int t; void print(int l,int r)//根据寻找的路径打印 { if(l>r) return; if(l==r) { if(a[l]=='('||a[l]==')') printf("()"); else printf("[]"); return; } if((a[l]=='('&&a[r]==')'||a[l]=='['&&a[r]==']')&&dp[l][r]==dp[l+1][r-1]) { printf("%c",a[l]); print(l+1,r-1); printf("%c",a[r]); return; } for(int k=l;k<r;k++) if(dp[l][r]==dp[l][k]+dp[k+1][r]) { print(l,k); print(k+1,r); return; } } int main() { scanf("%d",&t); gets(a+1); while(t--) { gets(a+1); gets(a+1);//注意，输入回车，输出回车 int n=strlen(a+1); memset(dp,0,sizeof(dp)); for(int i=1;i<=n;i++) dp[i][i]=1; for(int l=2;l<=n;l++) { for(int i=1,j=l;j<=n;i++,j++) { if(a[i]=='('&&a[j]==')'||a[i]=='['&&a[j]==']') { dp[i][j]=dp[i+1][j-1]; } else dp[i][j]=inf; for(int k=i;k<j;k++) dp[i][j]=min(dp[i][j],dp[i][k]+dp[k+1][j]);//括号相当于不增加值，同样长度的字符串，当然有括号的更小 } } print(1,n); puts(""); if(t) puts(""); } return 0; }
转载于:https://www.cnblogs.com/Wangwanxiang/p/7367701.html
