首页 > 代码库 > UVa 1626 (输出方案) Brackets sequence
UVa 1626 (输出方案) Brackets sequence
正规括号序列定义为：
- 空序列是正规括号序列
- 如果S是正规括号序列，那么[S]和(S)也是正规括号序列
- 如果A和B都是正规括号序列，则AB也是正规括号序列
输入一个括号序列，添加尽量少的括号使之成为正规括号序列，并输出最优方案，多解的话输出任意一个即可。
设d(i, j)表示字符串s[i]~s[j]至少添加的括号的数量，则转移如下：
- S形如[S‘]或(S‘)，则转移到d(i+1, j-1)
- 如果S至少有两个字符，将其分为AB，转移到min{d(i, j), d(A) + d(B)}
不管是否满足第一条都要尝试第二种转移，因为[][]可能经过第一条转移到][
打印的时候重新检查一下最优决策。
1 //#define LOCAL 2 #include <cstdio> 3 #include <cstring> 4 #include <algorithm> 5 using namespace std; 6 7 const int maxn = 110; 8 char s[maxn]; 9 int d[maxn][maxn], n;10 11 bool match(char a, char b)12 {13 return (a == ‘(‘ && b == ‘)‘) || (a == ‘[‘ && b == ‘]‘);14 }15 16 void dp()17 {18 for (int i = 0; i < n; ++i)19 {20 d[i+1][i] = 0; //对应空串21 d[i][i] = 1;22 }23 for (int i = n-2; i >= 0; --i)24 {25 for (int j = i+1; j < n; ++j)26 {27 d[i][j] = n;28 if(match(s[i], s[j]))29 d[i][j] = min(d[i][j], d[i+1][j-1]);30 for (int k = i; k < j; ++k)31 d[i][j] = min(d[i][j], d[i][k] + d[k+1][j]);32 }33 }34 }35 36 void print(int i, int j)37 {38 if(i > j) return;39 if(i == j)40 {41 if(s[i] == ‘(‘ || s[i] == ‘)‘) printf("()");42 else printf("[]");43 return;44 }45 int ans = d[i][j];46 if(match(s[i], s[j]) && ans == d[i+1][j-1])47 {48 printf("%c", s[i]);49 print(i+1, j-1);50 printf("%c", s[j]);51 return;52 }53 for (int k = i; k < j; ++k)54 {55 if(ans == d[i][k] + d[k+1][j])56 {57 print(i, k);58 print(k+1, j);59 return;60 }61 }62 }63 64 void readline(char* s)65 {66 fgets(s, maxn, stdin);67 }68 69 int main(void)70 {71 #ifdef LOCAL72 freopen("1626in.txt", "r", stdin);73 #endif74 75 int T;76 readline(s);77 sscanf(s, "%d", &T);78 readline(s);79 while(T--)80 {81 readline(s);82 n = strlen(s) - 1; //去掉最后的换行符 83 memset(d, -1, sizeof(d));84 dp();85 print(0, n-1);86 puts("");87 if(T) puts("");88 readline(s);89 }90 91 return 0;92 }
UVa 1626 (输出方案) Brackets sequence
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。