题目传送门(洛谷) 题目传送门(UVA)
解题思路
很显然是一个区间dp，当然记忆化搜索完全可以AC，这里说一下区间dp。
区间dp的重要特征就是需要枚举中间节点k
看一看这道题，用f[i][j]表示从i...j组成合法序列需要添加括号的个数，
很显然，当s[i]==s[j]时，f[i][j]=f[i+1][j-1]，然后枚举中间点k，就能写出动态转移方程：f[i][j]=max(f[i][j],f[i][k]+f[k+1][j])
为了保证在求f[i][j]时f[i+1][j-1]、f[i][k]、f[k+1][j]已经求完，第一层的i必须要倒着枚举，第二层j一定要正着枚举（手推一下就明白了QAQ）
求出f数组后，就要考虑怎样输出，因为输出的形式是(S)或[S],所以很显然用递归输出，加几个if特判就OK了。
然而，这道题我写完代码后一直是wa，三十分钟后才发现问题。
在读入t时，我一开始用的是cin>>t;看了题解后，终于发现应该是cin>>t后面再加上getchar()；为什么呢？（正在等待Candy？学长回复）
AC代码
1 #include<iostream>
2 #include<algorithm>
3 #include<cmath>
4 #include<cstdio>
5 #include<cstring>
6 #include<cstdlib>
7 #include<queue>
8 #include<set>
9 #include<map>
10 #include<vector>
11 #include<iomanip>
12 #include<ctime>
13 #include<stack>
14 using namespace std;
15 string s;
16 int t,len,f[105][105];
17 void print(int l,int r){
18 if(l>r) return;
19 if(l==r){
20 if(s[l]=='('||s[l]==')') printf("()");
21 if(s[l]=='['||s[l]==']') printf("[]");
22 return;
23 }
24 if((f[l][r]==f[l+1][r-1])&&((s[l]=='('&&s[r]==')')||(s[l]=='['&&s[r]==']'))){
25 printf("%c",s[l]);
26 print(l+1,r-1);
27 printf("%c",s[r]);
28 return;
29 }
30 for(int k=l;k<r;k++){
31 if(f[l][r]==f[l][k]+f[k+1][r]){
32 print(l,k);
33 print(k+1,r);
34 return;//找到一个正解就输出并return
35 }
36 }
37 }
38 int main()
39 {
40 scanf("%d",&t);
41 getchar();
42 while(t--){
43 memset(f,0x3f,sizeof(f));
44 getline(cin,s);
45 getline(cin,s);
46 len=s.length();
47 if(len==0){
48 printf("\n\n");
49 continue;
50 }
51 f[0][0]=0;
52 for(int i=1;i<len;i++) f[i][i]=1,f[i][i-1]=0;
53 for(int i=len-1;i>=0;i--){
54 for(int j=i+1;j<len;j++){
55 if((s[i]=='('&&s[j]==')')||(s[i]=='['&&s[j]==']')) f[i][j]=min(f[i][j],f[i+1][j-1]);
56 for(int k=i;k<j;k++) f[i][j]=min(f[i][j],f[i][k]+f[k+1][j]);
57 }
58 }
59 print(0,len-1);
60 printf("\n");
61 if(t) printf("\n");
62 }
63 return 0;
64 }