链接:
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("\n"); 55 if(T) printf("\n"); 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("\n"); 61 if(T) printf("\n"); 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("\n"); 60 if(T) printf("\n"); 61 } 62 return 0; 63 }