首页 > 代码库 > POJ 1141 Brackets Sequence

POJ 1141 Brackets Sequence

2024-08-16 00:18:19   227人阅读

Brackets Sequence

Time Limit: 1000MS Memory Limit: 65536K
Total Submissions: 30738 Accepted: 8817 Special Judge

Description

Let us define a regular brackets sequence in the following way:

1. Empty sequence is a regular sequence.
2. If S is a regular sequence, then (S) and [S] are both regular sequences.
3. If A and B are regular sequences, then AB is a regular sequence.

For example, all of the following sequences of characters are regular brackets sequences:

(), [], (()), ([]), ()[], ()[()]

And all of the following character sequences are not:

(, [, ), )(, ([)], ([(]

Some sequence of characters ‘(‘, ‘)‘, ‘[‘, and ‘]‘ is given. You are to find the shortest possible regular brackets sequence, that contains the given character sequence as a subsequence. Here, a string a1 a2 ... an is called a subsequence of the string b1 b2 ... bm, if there exist such indices 1 = i1 < i2 < ... < in = m, that aj = bij for all 1 = j = n.

Input

The input file contains at most 100 brackets (characters ‘(‘, ‘)‘, ‘[‘ and ‘]‘) that are situated on a single line without any other characters among them.

Output

Write to the output file a single line that contains some regular brackets sequence that has the minimal possible length and contains the given sequence as a subsequence.

Sample Input

([(]

Sample Output

()[()]

Source

Northeastern Europe 2001
 
题目大意：输入一个长度不超过100的括号序列，添加尽量少的括号，使其得到一个合法的括号序列，并且输出这个合法的括号序列。如果存在多个解，输出任意一个合法的括号序列即可。关于合法的括号序列的定义，参见我的另一篇博客：http://www.cnblogs.com/Silenceneo-xw/p/5936944.html，在此不再赘述。
 
解题思路：与POJ 2955 Brackets这题一样，是一个区间DP的题。思想很类似，但有些许差异。设dp[l][r]表示区间[l,r]内至少需要增加的括号数，则状态转移如下：
1、l==r时，dp[l][r]显然为1；
2、l与r匹配时，dp[l][r] = min(dp[l][r], dp[l+1][r-1])；
3、l与r不匹配时，可将区间[l,r]分成两个区间[l,mid]和[mid+1,r]，其中l<=mid<r。
注意：不管上述2是否满足，都要去尝试上述3，否则就会出现"[][]"转移到"]["的情况，这样就只能够添加两个括号了。还有一个注意点就是，当l>r时，要更新dp[l][r]=0，否则在输出结果时，类似"[][]"的结果输不出来，因为不符合判断条件。详见代码。
 
附上AC代码：
技术分享
 1 #include <cstdio> 2 #include <cstring> 3 #include <algorithm> 4 using namespace std; 5 const int maxn = 105; 6 const int inf = 0x3f3f3f3f; 7 char str[maxn]; 8 int dp[maxn][maxn]; 9 10 bool match(char a, char b){11     return (a==‘(‘&&b==‘)‘) || (a==‘[‘&&b==‘]‘);12 }13 14 int dfs(int l, int r){15     if (l > r)16         return dp[l][r] = 0;17     if (l == r)18         return dp[l][r] = 1;19     if (dp[l][r] != inf)20         return dp[l][r];21     int ans = dp[l][r];22     if (match(str[l], str[r]))23         ans = min(ans, dfs(l+1, r-1));24     for (int i=l; i<r; ++i)25         ans = min(ans, dfs(l, i)+dfs(i+1, r));26     return dp[l][r] = ans;27 }28 29 void print(int l, int r){30     if (l > r)31         return ;32     if (l == r){33         if (str[l]==‘(‘ || str[r]==‘)‘)34             printf("()");35         else36             printf("[]");37         return ;38     }39     int ans = dp[l][r];40     if (match(str[l], str[r]) && ans==dp[l+1][r-1]){41         putchar(str[l]);42         print(l+1, r-1);43         putchar(str[r]);44         return ;45     }46     for (int i=l; i<r; ++i)47         if (ans == dp[l][i]+dp[i+1][r]){48             print(l, i);49             print(i+1, r);50             return ;51         }52 }53 54 int main(){55     while (fgets(str, maxn, stdin)){56         int n = strlen(str);57         str[n-1] = ‘\0‘;58         --n;59         memset(dp, inf, sizeof(dp));60         dfs(0, n-1);61         print(0, n-1);62         putchar(‘\n‘);63     }64     return 0;65 }
View Code

 

POJ 1141 Brackets Sequence


联系
我们