DP Brackets Sequence POJ 1141

题意就是给一个字符串，字符串中只含(,),[,].加入这四种字符，要你插入一些字符，使得这段字符串是正确的，要求加入的字符数目最少。正确的定义就是一般意义上的正确。。。。

比如([)就是错误的，（[]）就是正确的。

题目要求的是输出加入最少数量的字符后，字符串正确了，输出该正确的字符串，感觉DP一般会让你输出最少加多少个字符啊，结果让我输正确的结果，蒙了，我不会，就抄了别人的，下面的代码是别人的，但是我忘了从哪里抄来的了，反正是百度的。。。。。希望原作者勿怪。。。

贴代码：注意注释

View Code

 1 //如果原括号出现（S'）,[S'],只需用最少的步数把S'化为正确的即可。
 2 //如果原括号出现(S',[S',S'],S')，那么再先把S'已最少的步数化为正确的后，再添上剩下的半边括号即可
 3 //任何一段长度大于1的序列，都可以化作两部分，S' = S1' + S2'，就以最少的步数将S1'和S2'化为正确的
 4 //最优化原理：原问题最优，当且仅当子问题最优。
 5 #include <cstdio>
 6 #include <cstring>
 7 #define INF 0x7fffffff
 8 #define MAXN 110
 9 char s[MAXN];
10 int path[MAXN][MAXN];  //记录路径
11 void output(int i,int j)
12 {
13     if(i > j) return;
14     if(i == j)//添括号
15     {
16         if(s[i] == '[' || s[i] == ']')
17             printf("[]");
18         else printf("()");
19     }
20     else if(path[i][j] == -1)//s[i]和s[j]本来就是一对匹配的括号
21     {
22         printf("%c",s[i]);
23         output(i+1,j-1);
24         printf("%c",s[j]);
25     }
26     else
27     {
28         output(i,path[i][j]);
29         output(path[i][j]+1,j);
30     }
31 }
32 int main()
33 {
34 //    freopen("in.cpp","r",stdin);
35     int d[MAXN][MAXN];//d[i][j]表示从位置i到j最少的添加括号的次数
36     while(gets(s))
37     {
38         int n = strlen(s);
39         if(n == 0)
40         {
41             puts("");
42             continue;
43         }
44         memset(d,0,sizeof(d));
45         for(int i=0; i<n; ++i)//自己到自己，总得添一个
46             d[i][i] = 1;
47         for(int p=1; p<n; ++p)//区间的长度从1到n-1
48         {
49             for(int i=0; i<n-p; ++i)
50             {
51                 int j = i+p;
52                 d[i][j] = INF;
53                 if((s[i] == '(' && s[j] == ')') || (s[i] =='[' && s[j] == ']'))
54                 {
55                     if(d[i][j] > d[i+1][j-1])
56                         d[i][j] = d[i+1][j-1],path[i][j] = -1;
57                 }
58                 for(int k=i; k<j; ++k)
59                 {
60                     if(d[i][j] > d[i][k] + d[k+1][j])
61                         d[i][j] = d[i][k] + d[k+1][j] ,path[i][j] = k;
62                 }
63             }
64         }
65         output(0,n-1);
66         puts("");
67     }
68     return 0;
69 }