poj1141：Brackets Sequence

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

()[()]
题解
刘汝佳的书写的很详细，我就不再解释了

 1 #include<cstdio>
 2 #include<algorithm>
 3 #include<cstring>
 4 using namespace std;
 5 char str[105];
 6 int f[105][105];
 7 bool ok(int l,int r)
 8 {
 9     if(str[l]=='('&&str[r]==')')return true;
10     if(str[l]=='['&&str[r]==']')return true;
11     return false;
12 }
13 void print(int l,int r)
14 {
15     if(l>r)return ;
16     if(l==r)
17     {
18         if(str[l]=='('||str[l]==')')printf("()");
19         else printf("[]");
20         return ;
21     }
22     int ans=f[l][r];
23     if(ans==f[l+1][r-1]&&ok(l,r))
24     {
25         printf("%c",str[l]);print(l+1,r-1);printf("%c",str[r]); 
26         return ;
27     }
28     for(int k=l ; k<r ; ++k)
29         if(ans==f[l][k]+f[k+1][r])
30         {
31             print(l,k);
32             print(k+1,r);
33             return ;
34         }
35 }
36 int main()
37 {
38     gets(str);
39     int len=strlen(str);
40     if(!len)
41     {
42         printf("
");
43         return 0;
44     }
45     for(int i=0 ; i < len ; ++i )
46         f[i][i]=1;
47     for(int i=len-2 ; i>=0 ; --i)
48         for(int j=i+1 ; j<len ; ++j)
49         {
50             f[i][j]=len;
51             if(ok(i,j))f[i][j]=min(f[i][j],f[i+1][j-1]);
52             for(int k=i ; k<j ; ++k)
53                 f[i][j]=min(f[i][j],f[i][k]+f[k+1][j]);
54         }
55     print(0,len-1);
56     printf("
");
57     return 0;
58 }