POJ 1141
给一段括号序列，要求增加最少的括号，使之合法，输出序列。
dp[i][j]表示使给定序列的i到j成为合法序列所需添加的最少括号数，dp[0][length-1]即是答案，转移的话，如果s[i]和s[j]可以匹配那么dp[i][j] = dp[i+1][j-1]，否则就考虑在中间选择一个位置m，使分割成的两个序列各自成为合法序列。方案的话就是多开一个数组记录然后递归输出。状态是从长度小的序列转移到长度长的序列，所以两层循环，外层枚举长度，内层枚举头位置即可。写成记忆化搜索简单一点，就是稍微慢些。
代码有点磨叽。
1 #include2 #include 3 #include 4 using namespace std; 5 6 7 char s[200]; 8 char mat[300]; 9 int d[200][200], g[200][200]; 10 bool pre[300], nex[300]; 11 bool match(int a, int b, char s[]) 12 { 13 if (s[a] == '(' && s[b] == ')') return true; 14 if (s[a] == '{ ' && s[b] == '}') return true; 15 if (s[a] == '[' && s[b] == ']') return true; 16 return false; 17 } 18 void output(int l, int r) 19 { 20 if (l > r) return; 21 if (g[l][r] == 0){ 22 printf("%c", s[l]); 23 output(l+1, r-1); 24 printf("%c", s[r]); 25 } 26 else if (g[l][r] == -1){ 27 if (pre[s[l]]) 28 printf("%c%c", s[l], mat[s[l]]); 29 else 30 printf("%c%c", mat[s[l]], s[l]); 31 output(l+1, r); 32 } 33 else if (g[l][r] == -2){ 34 output(l, r-1); 35 if (pre[s[r]]) 36 printf("%c%c", s[r], mat[s[r]]); 37 else 38 printf("%c%c", mat[s[r]], s[r]); 39 } 40 else if (g[l][r] == -3){ 41 printf("%c%c", s[l], s[r]); 42 } 43 else{ 44 output(l, g[l][r]); 45 output(g[l][r]+1, r); 46 } 47 } 48 int main() 49 { 50 memset(pre, false, sizeof(pre)); 51 memset(nex, false, sizeof(nex)); 52 pre['('] = 1; pre['{ '] = 1; pre['['] = 1; 53 nex[')'] = 1; nex['}'] = 1; nex[']'] = 1; 54 mat['('] = ')'; mat[')'] = '('; 55 mat['{ '] = '}'; mat['}'] = '{ '; 56 mat['['] = ']'; mat[']'] = '['; 57 while(gets(s)) 58 { 59 memset(d, 127, sizeof(d)); 60 int len = strlen(s); 61 for (int i = 0; i < len; i++){ 62 d[i][i] = 1; 63 g[i][i] = -1; 64 } 65 for (int i = 0; i < len-1; i++) 66 if (match(i, i+1, s)){ 67 d[i][i+1] = 0; 68 g[i][i+1] = -3; 69 } 70 for (int k = 1; k < len; k++) 71 for (int i = 0; i < len; i++){ 72 int j = i + k; 73 if (j >= len) break; 74 int tmp = d[i+1][j-1];// + 2 * (1 - match(i, j, s)); 75 if (match(i, j, s) && tmp < d[i][j]){ 76 d[i][j] = tmp; 77 g[i][j] = 0; 78 } 79 tmp = d[i+1][j]+1; 80 if (tmp < d[i][j]){ 81 d[i][j] = tmp; 82 g[i][j] = -1; 83 } 84 tmp = d[i][j-1]+1; 85 if (tmp < d[i][j]){ 86 d[i][j] = tmp; 87 g[i][j] = -2; 88 } 89 for (int m = i; m < j; m++){ 90 tmp = d[i][m] + d[m+1][j]; 91 if (tmp < d[i][j]){ 92 d[i][j] = tmp; 93 g[i][j] = m; 94 } 95 } 96 } 97 // for (int i = 0; i < len; i++) 98 // for (int j = i; j < len; j++) 99 // printf("%d %d %d\n", i, j, d[i][j]);100 // printf("%d\n", d[0][len-1]); 101 output(0, len-1);102 printf("\n");103 }104 return 0;105 }
TC SRM 628 DIV 2 500 Points
给一段括号序列，其中还有不超过5个通配符，问是否合法。
因为通配符不超过5个，所以可以直接枚举其可能(6的5次方)，然后用栈来判断，如果是前括号则压入栈，如果是后括号则和栈顶匹配，可以弹出栈顶，否则矛盾退出。或者也是和上题一样的dp思路，最后看如果最少增加括号为0，即是合法。
1 #include2 #include 3 #include 4 #include 5 using namespace std; 6 7 int d[200][200]; 8 bool match(int a, int b, string s) 9 {10 if (s[a] == 'X')11 if (s[b] == '}' || s[b] == ')' || s[b] == ']' || s[b] == 'X') return true;12 if (s[b] == 'X')13 if (s[a] == '(' || s[a] == '{ ' || s[a] == '[' || s[a] == 'X') return true;14 if (s[a] == '(' && s[b] == ')') return true;15 if (s[a] == '{ ' && s[b] == '}') return true;16 if (s[a] == '[' && s[b] == ']') return true;17 return false;18 }19 20 class BracketExpressions{21 public:22 string ifPossible(string s)23 { 24 int len = s.length();25 for (int i = 0; i < len; i++)26 d[i][i] = 1;27 for (int i = 0; i < len-1; i++) if (match(i, i+1, s))28 d[i][i+1] = 0;29 for (int k = 1; k < len; k++)30 for (int i = 0; i < len; i++){31 int j = i + k;32 if (j >= len) break;33 d[i][j] = 214748360;34 if (match(i, j, s))35 d[i][j] = d[i+1][j-1];36 for (int m = i; m < j; m++)37 d[i][j] = min(d[i][j], d[i][m] + d[m+1][j]);38 }39 if (d[0][len-1] == 0) return "possible";40 else return "impossible";41 }42 }