POJ 1141 Brackets Sequence，pojbrackets
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 else
36 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
