UVa 1626

链接：

https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=4501

题意：

定义如下正规括号序列（字符串）：
1.空序列是正规括号序列。
2.如果S是正规括号序列，那么(S)和[S]也是正规括号序列。
3.如果A和B都是正规括号序列，那么AB也是正规括号序列。
输入一个长度不超过100的，由“(”、“)”、“[”、“]”构成的序列，添加尽量少的括号，得到一个正规序列。
如有多解，输出任意一个序列即可。

分析：

设串S至少需要增加d(S)个括号，转移如下：
1.如果S形如(S′)或者[S′]，转移到d(S′)。
2.如果S至少有两个字符，则可以分成AB，转移到d(A)＋d(B)。
边界是：S为空时d(S)=0，S为单字符时d(S)=1。
注意：不管S是否满足第一种，都要尝试第二种转移，否则“[][]”会转移到“][”，然后就只能加两个括号了。
设d(i,j)表示子串S[i～j]至少需要添加几个括号。
对于第一种，状态转移方程为：d(i,j) = d(i+1, j-1)。
对于第二种，状态转移方程为：d(i,j) = min{d(i, k) + d(k+1, j) | i ≤ k < j}。
可以在打印解的时候重新检查一下哪个决策最好。
最后，这题的输入输出有点坑。。。

代码：

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <algorithm>
 4 using namespace std;
 5 
 6 const int UP = 100 + 5;
 7 char s[UP];
 8 int d[UP][UP]; // d[L][R]表示子串s[L～R]至少需要添加几个括号
 9 
10 bool match(char L, char R){
11     return (L == '(' && R == ')') || (L == '[' && R == ']');
12 }
13 
14 void dynamic_programming(int len){
15     for(int i = 0; i < len; i++){
16         d[i][i] = 1;
17         d[i+1][i] = 0;
18     }
19     for(int L = len - 2; L >= 0; L--){
20         for(int R = L + 1; R < len; R++){
21             int& v = d[L][R];
22             v = match(s[L], s[R]) ? d[L+1][R-1] : 12345;
23             for(int M = L; M < R; M++) v = min(v, d[L][M] + d[M+1][R]);
24         }
25     }
26 }
27 
28 void output(int L, int R){
29     if(L > R) return;
30     if(L == R){
31         if(s[L] == '(' || s[L] == ')') printf("()");
32         else printf("[]");
33         return;
34     }
35     int ans = d[L][R];
36     if(match(s[L], s[R]) && d[L+1][R-1] == ans){
37         printf("%c", s[L]);  output(L+1, R-1);  printf("%c", s[R]);
38         return;
39     }
40     for(int M = L; M < R; M++) if(d[L][M] + d[M+1][R] == ans){
41         output(L, M);  output(M+1, R);
42         return;
43     }
44 }
45 
46 int main(){
47     int T;
48     scanf("%d", &T);
49     getchar();
50     while(T--){
51         gets(s);  gets(s);
52         int len = strlen(s);
53         dynamic_programming(len);
54         output(0, len - 1);  printf("
");
55         if(T) printf("
");
56     }
57     return 0;
58 }

最后，再贴一下我一开始的代码，状态的转移有点不同：当s[L]与s[M]不匹配时，d(L,M)转移到d(L+1,M)+1。

递推写法：

 1 #include <cstdio>
 2 #include <cstring>
 3 
 4 const int UP = 100 + 5;
 5 char s[UP];
 6 int d[UP][UP], ans[UP][UP];
 7 
 8 int diff(int L, int R){
 9     if(s[L] == '(') return s[R] != ')';
10     if(s[L] == '[') return s[R] != ']';
11     return 1;
12 }
13 
14 void dynamic_programming(int len){
15     for(int i = 0; i < len; i++){
16         d[i][i] = 1;
17         d[i+1][i] = 0;
18     }
19     for(int L = len - 2; L >= 0; L--){
20         for(int R = L + 1; R < len; R++){
21             d[L][R] = 12345;
22             for(int M = L; M <= R; M++){
23                 int f = diff(L, M);
24                 int v = f + d[L+1][M-1+f] + d[M+1][R];
25                 if(d[L][R] > v){
26                     d[L][R] = v;
27                     ans[L][R] = M;
28                 }
29             }
30         }
31     }
32 }
33 
34 void output(int L, int R){
35     if(L > R) return;
36     if(L == R){
37         if(s[L] == '(' || s[L] == ')') printf("()");
38         else printf("[]");
39         return;
40     }
41     int M = ans[L][R];
42     if(L == M){
43         output(L, M);  output(M+1, R);
44         return;
45     }
46     printf("%c", s[L]);
47     if(!diff(L, M)) output(L+1, M-1), printf("%c", s[M]);
48     else output(L+1, M), printf("%c", s[L] == '(' ? ')' : ']');
49     output(M+1, R);
50 }
51 
52 int main(){
53     int T;
54     scanf("%d", &T);
55     getchar();
56     while(T--){
57         gets(s);  gets(s);
58         int len = strlen(s);
59         dynamic_programming(len);
60         output(0, len - 1);  printf("
");
61         if(T) printf("
");
62     }
63     return 0;
64 }

记忆化写法（比递推写法慢几倍）：

 1 #include <cstdio>
 2 #include <cstring>
 3 
 4 const int INF = 0x3f3f3f3f;
 5 const int UP = 100 + 5;
 6 int d[UP][UP], ans[UP][UP];
 7 char s[UP];
 8 
 9 int diff(int L, int R){
10     if(s[L] == '(') return s[R] != ')';
11     if(s[L] == '[') return s[R] != ']';
12     return 1;
13 }
14 
15 int dp(int L, int R){
16     if(L > R) return 0;
17     if(L == R) return 1;
18     int& v = d[L][R];
19     if(v != INF) return v;
20 
21     for(int M = L; M <= R; M++){
22         int f = diff(L, M);
23         int res = f + dp(L+1, M-1+f) + dp(M+1, R);
24         if(v > res){
25             v = res;
26             ans[L][R] = M;
27         }
28     }
29     return v;
30 }
31 
32 void output(int L, int R){
33     if(L > R) return;
34     if(L == R){
35         if(s[L] == '(' || s[L] == ')') printf("()");
36         else printf("[]");
37         return;
38     }
39     int M = ans[L][R];
40     if(L == M){
41         output(L, M);  output(M+1, R);
42         return;
43     }
44     printf("%c", s[L]);
45     if(!diff(L, M)) output(L+1, M-1), printf("%c", s[M]);
46     else output(L+1, M), printf("%c", s[L] == '(' ? ')' : ']');
47     output(M+1, R);
48 }
49 
50 int main(){
51     int T;
52     scanf("%d", &T);
53     getchar();
54     while(T--){
55         gets(s);  gets(s);
56         memset(d, INF, sizeof(d));
57         dp(0, strlen(s) - 1);
58         output(0, strlen(s) - 1);
59         printf("
");
60         if(T) printf("
");
61     }
62     return 0;
63 }