区间DP POJ 1141 Brackets Sequence

Brackets Sequence Time Limit: 1000MS   Memory Limit: 65536K Total Submissions: 29520   Accepted: 8406   Special Judge Description Let us define a regular brackets sequence in the following way: 1. Empty sequence is a regular sequence.  2. If S is a regular sequence, then (S) and [S] are both regular sequences.  3. If A and B are regular sequences, then AB is a regular sequence. For example, all of the following sequences of characters are regular brackets sequences: (), [], (()), ([]), ()[], ()[()] And all of the following character sequences are not: (, [, ), )(, ([)], ([(] Some sequence of characters '(', ')', '[', and ']' is given. You are to find the shortest possible regular brackets sequence, that contains the given character sequence as a subsequence. Here, a string a1 a2 ... an is called a subsequence of the string b1 b2 ... bm, if there exist such indices 1 = i1 < i2 < ... < in = m, that aj = bij for all 1 = j = n. Input The input file contains at most 100 brackets (characters '(', ')', '[' and ']') that are situated on a single line without any other characters among them. Output Write to the output file a single line that contains some regular brackets sequence that has the minimal possible length and contains the given sequence as a subsequence. Sample Input ([(] Sample Output ()[()] 　　　　 /*对于DP题目需要记录到底是怎样得到结果的，不一定了可以通过记录信息直接得到，可以选择数组记录其他有用信息，可以写递归来找出最后的答案。*/ #define N 111 #include<iostream> using namespace std; #include<cstring> #include<cstdio> #define inf (1<<31)-1 int f[N][N],pos[N][N],lens; char s[N]; void print(int l,int r)/*输出序列的过程*/ { if(l<=r)/*一定要有这一句，否则对于相邻的‘（）’，就会死循环了*/ { if(l==r)/*能到这一步，说明只能补上括号了*/ { if(s[l]=='('||s[l]==')') printf("()"); if(s[l]=='['||s[l]==']') printf("[]"); } else { if(pos[l][r]==-)/*说明该区间最左括号与最右匹配*/ { printf("%c",s[l]); print(l+,r-);/**/ printf("%c",s[r]); } else { print(l,pos[l][r]); print(pos[l][r]+,r); } } } } int main() { // freopen("bracket.in","r",stdin); // freopen("bracket.out","w",stdout); scanf("%s",s+); lens=strlen(s+); for(int i=;i<=lens;++i) f[i][i]=; /* for(int i=lens-1;i>=1;--i) for(int j=i+1;j<=lens;++j) { f[i][j]=inf; if(((s[i]=='('&&s[j]==')')||(s[i]=='['&&s[j]==']'))) { f[i][j]=f[i+1][j-1]; pos[i][j]=-1; } for(int k=i;k<=j-1;++k) { if(f[i][j]>f[i][k]+f[k+1][j]) { f[i][j]=f[i][k]+f[k+1][j]; pos[i][j]=k; } } }这两种都是可以得出正确答案的，但是我建议使用下面的，对于区间DP，最外层循环最好枚举区间长度，内层枚举区间*/ for(int k=;k<lens;++k) for(int i=,j=i+k;j<=lens&&i<=lens;++j,++i) { f[i][j]=inf; if((s[i]=='('&&s[j]==')')||(s[i]=='['&&s[j]==']')) { f[i][j]=f[i+][j-]; pos[i][j]=-; } /*不要加else，因为即使当前区间的最左和最右匹配，也不一定比放弃他们匹配优*/ for(int k=i;k<=j-;++k) { if(f[i][j]>f[i][k]+f[k+][j]) { f[i][j]=f[i][k]+f[k+][j]; pos[i][j]=k; } } } print(,lens); printf("\n");/*坑爹的POJ，没有这句，一直没对*/ //fclose(stdin);fclose(stdout); return ; }