poj_1141

括号匹配，结果为匹配后的串

一、记忆化搜索(search with finger)：

从[0, strlen(s)-1] 开始搜索，缩短区间，期间记录搜索过的值，防止重复

cut[l][r]代表区间[l, r]中需要从哪里分割，为输出

串长不超过100 复杂度可以接受

 1 // Brackets sequence
 2 // Search with fingers
 3 
 4 #include <iostream>
 5 #include <string>
 6 #include <algorithm>
 7 #include <cstring>
 8 #include <cstdio>
 9 
10 #define MAXN 100
11 
12 int n, dp[MAXN+10][MAXN+10], cut[MAXN+10][MAXN+10];
13 char s[111];
14 
15 int SearchWithFinger(int l, int r)
16 {
17     if(l > r)
18         return dp[l][r] = 0;
19     if(l == r)
20         return dp[l][r] = 1;
21     if(dp[l][r]!=-1)
22         return dp[l][r];
23 
24     int num = 1<<30;
25     if( (s[l]=='('&&s[r]==')')||(s[l]=='['&&s[r]==']') )
26         num = std::min(num, SearchWithFinger(l+1, r-1));
27     else if(s[l]=='('||s[l]=='[')
28         num = std::min(num, SearchWithFinger(l+1, r)+1);
29     else if(s[r]==')'||s[r]==']')
30         num = std::min(num, SearchWithFinger(l, r-1)+1);
31 
32     for(int m = l; m < r; ++m){
33         int temp = SearchWithFinger(l, m) + SearchWithFinger(m+1, r);
34         if(num >= temp){
35             num = temp;
36             cut[l][r] = m;
37         }
38     }
39 
40     return dp[l][r] = num;
41 
42 }
43 
44 void PrintOut(int l, int r)
45 {
46     if(l > r)
47         return;
48     if(l == r){
49         if(s[l]=='('||s[l]==')')
50             printf("()");
51         if(s[l]=='['||s[l]==']')
52             printf("[]");
53     }
54     else{
55         if(cut[l][r] >= 0){
56             PrintOut(l, cut[l][r]);
57             PrintOut(cut[l][r]+1, r);
58         }
59         else{
60             if(s[l]=='(' ){
61                 printf("(");
62                 PrintOut(l+1, r-1);
63                 printf(")");
64             }
65             if(s[l]=='['){
66                 printf("[");
67                 PrintOut(l+1, r-1);
68                 printf("]");
69             }
70         }
71     }
72 
73 }
74 
75 int main(int argc, char const *argv[])
76 {
77     // freopen("in", "r", stdin);
78     // freopen("out", "w", stdout);
79     scanf("%d", &n);
80     getchar();
81     while(n--){
82 
83         getchar();
84         gets(s);
85     
86 
87         memset(dp, -1, sizeof(dp));
88         memset(cut, -1, sizeof(cut));
89 
90         SearchWithFinger(0, strlen(s)-1);
91 
92         PrintOut(0, strlen(s)-1);
93 
94         printf("
");
95         if(n)
96             printf("
");
97     }
98     return 0;
99 }

二、区间DP

dp[l][r]代表从区间[l, r]的串需要添加至少多少个括号才能匹配

枚举区间长度len ： 1 to strlen(s)-1

dp[i][i] = 0 任何一个单独的括号，都需要添加至少一个括号才能匹配

cut[l][r]意义同上

 1 // Brackets sequence
 2 // dynamic programming
 3 
 4 #include <cstdio>
 5 #include <cstring>
 6 #include <string>
 7 #include <algorithm>
 8 #include <iostream>
 9 
10 #define MAXN 100
11 
12 int n, dp[MAXN+5][MAXN+5], cut[MAXN+5][MAXN+5];
13 char s[MAXN+10];
14 
15 void PrintOut(int l, int r)
16 {
17     if(l > r)
18         return ;
19     if(l == r){
20         if(s[l]=='('||s[l]==')')
21             printf("()");
22         if(s[l]=='['||s[l]==']')
23             printf("[]");
24     }
25     else{
26         if(cut[l][r] >= 0){
27             PrintOut(l, cut[l][r]);
28             PrintOut(cut[l][r]+1, r);
29         }
30         else{
31             if(s[l]=='(' ){
32                 printf("(");
33                 PrintOut(l+1, r-1);
34                 printf(")");
35             }
36             if(s[l]=='['){
37                 printf("[");
38                 PrintOut(l+1, r-1);
39                 printf("]");
40             }
41         }
42     }
43 
44 }
45 
46 int main(int argc, char const *argv[])
47 {
48     // freopen("in", "r", stdin);
49 
50     while(gets(s)){
51 
52         memset(dp, 0, sizeof(dp));
53         memset(cut, -1, sizeof(cut));
54 
55         for(int i = 0; i < strlen(s); ++i)
56             dp[i][i] = 1;
57 
58         for(int len = 1; len < strlen(s); ++len){
59             for(int l = 0; l+len < strlen(s); ++l){
60                 int r = l+len;
61                 dp[l][r] = 1<<30;
62                 if( (s[l]=='('&&s[r]==')')||(s[l]=='['&&s[r]==']') )
63                     dp[l][r] = std::min(dp[l][r], dp[l+1][r-1]);
64                 else if(s[l]=='('||s[l]=='[')
65                     dp[l][r] = std::min(dp[l][r], dp[l+1][r]+1);
66                 else if(s[r]==')'||s[r]==']')
67                     dp[l][r] = std::min(dp[l][r], dp[l][r-1]+1);
68                 for(int m = l; m < r; ++m){
69                     if(dp[l][r] >= dp[l][m] + dp[m+1][r]){
70                         dp[l][r] = dp[l][m] + dp[m+1][r];
71                         cut[l][r] = m;
72                     }
73                 }
74             }
75         }
76         // printf("%d
", dp[0][strlen(s)-1]);
77         PrintOut(0, strlen(s)-1);
78         printf("
");
79     }
80     return 0;
81 }