1626 - 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 begins with a single positive integer on a line by itself indicating the number of the cases following, each of them as described below. This line is followed by a blank line, and there is also a blank line between two consecutive inputs.

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

Output

For each test case, the output must follow the description below. The outputs of two consecutive cases will be separated by a blank line.

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

1

([(]

Sample Output

()[()]

紫书上有详解＋代码，就不废话了直接贴代码：

 #include <iostream>

 #include <cstdio>

 #include <cstring>

 using namespace std;

 const int maxn = ;

 char s[maxn];

 int d[maxn][maxn];

 int n;

 inline bool match(char a,char b){

     if((a=='('&&b==')')||(a=='['&&b==']')) return true;

     else return false;

 }

 void dp(){

     for(int i=;i<n;i++){

         d[i+][i]=;

         d[i][i]=;

     }

     for(int i=n-;i>=;i--){

         for(int j=i+;j<n;j++){

             d[i][j]=maxn;

             if(match(s[i],s[j]))

                 d[i][j]=min(d[i][j],d[i+][j-]);

             for(int k=i;k<j;k++){

                 d[i][j]=min(d[i][j],d[i][k]+d[k+][j]);

             }

         }

     }

 }

 void print(int i,int j){

     if(i>j) return;

     if(i==j){

         if(s[i]=='('||s[i]==')') printf("()");

         else printf("[]");

         return;

     }

     int ans=d[i][j];

     if(match(s[i],s[j])&&ans==d[i+][j-]){

         printf("%c",s[i]);print(i+,j-);printf("%c",s[j]);

         return;

     }

     for(int k=i;k<j;k++){

         if(ans==d[i][k]+d[k+][j]){

             print(i,k);print(k+,j);

             return;

         }

     }

 }

 int main(int argc, const char * argv[]) {

     int T;

     scanf("%d",&T);

     getchar();

     while(T--){

         getchar();

         memset(s, , sizeof s);

         char ch;

         for(int i=;(ch=getchar())!='\n';i++){

             s[i]=ch;

         }

         n=strlen(s);

         dp();

         print(,n-);

         printf("\n");

         if(T!=) printf("\n");

     }

     return ;

 }

巴特西

1626 - Brackets sequence——［动态规划］

Input

Output

Sample Input

Sample Output

最新文章

热门文章