UVA1626 括号序列 Brackets sequence（区间dp）

题目传送门(洛谷)   题目传送门(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()；为什么呢？

终于发现困扰了我接近一个小时的问题根源了——

辣鸡洛谷出错题了！！样例中的t和第一组数据间有一行空格。。。（体现出看原题的重要性）

AC代码

 #include<iostream>

 #include<algorithm>

 #include<cmath>

 #include<cstdio>

 #include<cstring>

 #include<cstdlib>

 #include<queue>

 #include<set>

 #include<map>

 #include<vector>

 #include<iomanip>

 #include<ctime>

 #include<stack>

 using namespace std;

 string s;

 int t,len,f[][];

 void print(int l,int r){

     if(l>r) return;

     if(l==r){

         if(s[l]=='('||s[l]==')') printf("()");

         if(s[l]=='['||s[l]==']') printf("[]");

         return;

     }

     if((f[l][r]==f[l+][r-])&&((s[l]=='('&&s[r]==')')||(s[l]=='['&&s[r]==']'))){

         printf("%c",s[l]);

         print(l+,r-);

         printf("%c",s[r]);

         return;

     }

     for(int k=l;k<r;k++){

         if(f[l][r]==f[l][k]+f[k+][r]){

             print(l,k);

             print(k+,r);

             return;//找到一个正解就输出并return

         }

     }

 }

 int main()

 {

     scanf("%d",&t);

     getchar();

     while(t--){

         memset(f,0x3f,sizeof(f));

         getline(cin,s);

         getline(cin,s);

         len=s.length();

         if(len==){

             printf("\n\n");

             continue;

         }

         f[][]=;

         for(int i=;i<len;i++) f[i][i]=,f[i][i-]=;

         for(int i=len-;i>=;i--){

             for(int j=i+;j<len;j++){

                 if((s[i]=='('&&s[j]==')')||(s[i]=='['&&s[j]==']')) f[i][j]=min(f[i][j],f[i+][j-]);

                 for(int k=i;k<j;k++) f[i][j]=min(f[i][j],f[i][k]+f[k+][j]);

             }

         }

         print(,len-);

         printf("\n");

         if(t) printf("\n");

     }

     return ;

 }