1183. Brackets Sequence

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

Empty sequence is a regular sequence.
If S is a regular sequence, then (S) and [S] are both regular sequences.
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 a₁a₂...a_n is called a subsequence of the string b₁b₂...b_m, if there exist such indices 1 ≤ i₁ < i₂ < ... < i_n ≤ m, that a_j=b_{i_j} for all 1 ≤ j ≤ n.

Input

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

Output

Write 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	output
([(]	()[()]

Problem Author: Andrew Stankevich Problem Source: 2001-2002 ACM Northeastern European Regional Programming Contest

Tags: dynamic programming ()

Difficulty: 250 Printable version Submit solution Discussion (18) My submissions All submissions (5352) All accepted submissions (1722) Solutions rating (1349)

*****************************************************************************

题解：本题和石子合并问题和求矩阵代价类似，但在此过程中加了一个dir[][]寻找最优路径。俩字经典。

**************************************************************************************************

*****************************************************************************

  1 #include<iostream>
  2 #include<string>
  3 #include<cstring>
  4 #include<cstdio>
  5 #include<cmath>
  6 #include<cctype>
  7 #include<algorithm>
  8 #include<stack>
  9 #include<queue>
 10 #include<vector>
 11 using namespace std;
 12 int dp[1000][1000],i,j;
 13 string str;
 14 int n,k,t;
 15 int dir[1000][1000];
 16 void  init()
 17 {
 18     cin>>str;
 19     getchar();
 20     n=str.length();
 21     for(int i=n;i>=1;i--)
 22      str[i]=str[i-1];
 23     //for(i=1;i<=n;i++)
 24      //cout<<str[i];
 25     //cout<<endl;
 26     for(int i=1;i<=n;i++)
 27       dp[i][i]=1;
 28 }
 29 void  solve()
 30 {
 31     for(t=1;t<n;t++)
 32      for(i=1;i<=n-t;i++)
 33       {
 34           j=i+t;
 35           dp[i][j]=99999999;
 36           if((str[i]=='('&&str[j]==')')||(str[i]=='['&&str[j]==']'))
 37            {
 38                dp[i][j]=dp[i+1][j-1];
 39                dir[i][j]=0;
 40            }
 41           for(int k=i;k<j;k++)
 42             if(dp[i][k]+dp[k+1][j]<dp[i][j])
 43             {
 44               dp[i][j]=dp[i][k]+dp[k+1][j];
 45                dir[i][j]=k;
 46             }
 47 
 48             if(str[i]=='('||str[i]=='[')
 49                if(dp[i+1][j]+1<dp[i][j])
 50                 {
 51                      dp[i][j]=dp[i+1][j]+1;
 52                      dir[i][j]=-1;
 53                 }
 54             if(str[i]==')'||str[i]==']')
 55               if(dp[i][j-1]+1<dp[i][j])
 56                 {
 57                    dp[i][j]=dp[i][j-1]+1;
 58                     dir[i][j]=-2;
 59                 }
 60 
 61       }
 62 }
 63 void  print(int i,int j)
 64 {
 65     if(i>j)return;
 66     if(i==j)
 67     {
 68         if(str[i]=='('||str[i]==')')
 69           cout<<"()";
 70         else
 71            cout<<"[]";
 72 
 73     }
 74     else
 75       {
 76           if(dir[i][j]==0)
 77           {
 78              if(str[i]=='('&&str[j]==')')
 79              {
 80                  cout<<'(';
 81                  print(i+1,j-1);
 82                  cout<<')';
 83              }
 84              if(str[i]=='['&&str[j]==']')
 85               {
 86                   cout<<'[';
 87                   print(i+1,j-1);
 88                   cout<<']';
 89               }
 90           }
 91           if(dir[i][j]>0)
 92             {
 93               print(i,dir[i][j]);
 94               print(dir[i][j]+1,j);
 95             }
 96           if(dir[i][j]==-1)
 97            {
 98                if(str[i]=='[')
 99                  {
100                      cout<<str[i];
101                      print(i+1,j);
102                      cout<<']';
103                  }
104                if(str[i]=='(')
105                 {
106                     cout<<str[i];
107                     print(i+1,j);
108                     cout<<')';
109                 }
110            }
111           if(dir[i][j]==-2)
112           {
113               if(str[i]==']')
114                {
115                    cout<<'[';
116                    print(i,j-1);
117                    cout<<str[i];
118                }
119               if(str[i]==')')
120                 {
121                     cout<<'(';
122                     print(i,j-1);
123                     cout<<str[i];
124                 }
125           }
126       }
127 }
128 int main()
129 {
130     init();
131     solve();
132     print(1,n);
133     return 0;
134 }

View Code