We give the following inductive definition of a “regular brackets” sequence:

• the empty sequence is a regular brackets sequence,
• if s is a regular brackets sequence, then (s) and [s] are regular brackets sequences, and
• if a and b are regular brackets sequences, then ab is a regular brackets sequence.
• no other sequence is a regular brackets sequence

For instance, all of the following character sequences are regular brackets sequences:

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

while the following character sequences are not:

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

Given a brackets sequence of characters a₁a₂ … a_n, your goal is to find the length of the longest regular brackets sequence that is a subsequence of s. That is, you wish to find the largest m such that for indices i₁, i₂, …, i_m where 1 ≤ i₁ < i₂ < … < i_m ≤ n, a_i1a_i2 … a_im is a regular brackets sequence.

Given the initial sequence ([([]])], the longest regular brackets subsequence is [([])].

The input test file will contain multiple test cases. Each input test case consists of a single line containing only the characters (, ), [, and ]; each input test will have length between 1 and 100, inclusive. The end-of-file is marked by a line containing the word “end” and should not be processed.

For each input case, the program should print the length of the longest possible regular brackets subsequence on a single line.

 #include<iostream>

 #include<algorithm>

 #include<cstdio>

 #include<string.h>

 using namespace std;

 const int maxn=;

 char str[maxn];int length,dp[maxn][maxn];

 bool check(char ch1,char ch2){

     return (ch1=='('&&ch2==')')||(ch1=='['&&ch2==']');

 }

 int main(){

     while(~scanf("%s",str+)&&strcmp(str+,"end")){

         memset(dp,,sizeof(dp));length=strlen(str+);

         for(int len=;len<=length;++len){//枚举区间长度1~length

             for(int i=;i<=length-len;++i){//区间起点i

                 int j=i+len;//区间终点j

                 if(check(str[i],str[j]))dp[i][j]=dp[i+][j-]+;

                 for(int k=i;k<j;++k)//区间最值合并

                     dp[i][j]=max(dp[i][j],dp[i][k]+dp[k+][j]);

             }

         }

         printf("%d\n",dp[][length]);

     }

     return ;

 }

 #include<iostream>

 #include<algorithm>

 #include<cstdio>

 #include<string.h>

 using namespace std;

 const int maxn=;

 char str[maxn];int t,length,dp[maxn][maxn];

 bool check(char ch1,char ch2){

     return (ch1=='('&&ch2==')')||(ch1=='['&&ch2==']');

 }

 int main(){

     while(~scanf("%d",&t)){

         while(t--){

             scanf("%s",str+);

             memset(dp,,sizeof(dp));length=strlen(str+);

             for(int len=;len<=length;++len){//区间长度

                 for(int i=;i<=length-len;++i){//区间起点i

                     int j=i+len;//区间终点j

                     if(check(str[i],str[j]))dp[i][j]=dp[i+][j-]+;

                     for(int k=i;k<j;++k)//更新区间最值

                         dp[i][j]=max(dp[i][j],dp[i][k]+dp[k+][j]);

                 }

             }

             printf("%d\n",length-dp[][length]);

         }

     }

     return ;

 }

 #include<iostream>

 #include<algorithm>

 #include<cstdio>

 #include<string.h>

 using namespace std;

 const int maxn=;

 const int inf=0x7fffffff;

 char str[maxn];int t,length,dp[maxn][maxn];

 bool check(char ch1,char ch2){

     return (ch1=='('&&ch2==')')||(ch1=='['&&ch2==']');

 }

 int dfs(int x,int y){

     if(x>y)return ;

     else if(dp[x][y]>=)return dp[x][y];//表示已搜索过了，此时直接返回当前区间[x,y]的值

     else if(x==y)return dp[x][y]=;//单个字符时，需要增加的括号数为1

     else{

         int var=inf;//先初始化为无穷大

         if(check(str[x],str[y]))var=dfs(x+,y-);//如果能匹配，至少需要增加的括号数为上一个状态的值dp[x+1][y-1]

         for(int k=x;k<y;++k)

             var=min(var,dfs(x,k)+dfs(k+,y));//再更新当前区间[x,y]最少需要增加的括号数，由其子状态得来

         return dp[x][y]=var;//返回并且赋值

     }

 }

 int main(){

     while(~scanf("%d",&t)){

         while(t--){

             scanf("%s",str+);memset(dp,-,sizeof(dp));

             length=strlen(str+);

             printf("%d\n",dfs(,length));

         }

     }

     return ;

 }

 #include<iostream>

 #include<algorithm>

 #include<cstdio>

 #include<string.h>

 using namespace std;

 typedef long long LL;

 const int maxn=;

 int t,len;LL m;char str[maxn];LL dp[maxn][maxn],num[maxn][maxn];

 int main(){

     while(cin>>t){

         while(t--){

             cin>>(str+)>>m;len=strlen(str+);memset(dp,,sizeof(dp));memset(num,,sizeof(num));

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

                 num[i][i]=str[i]-'';//num[i,i]的值为其本身

                 for(int j=i+;j<=len;++j)//num[i][j]表示区间[i,j]组成对应的数

                     num[i][j]=num[i][j-]*+(str[j]-'');

                 dp[i][]=num[][i];//前i位插入0个乘号，其值为1~i对应的数即num[1][i]

             }

             for(int j=;j<m;++j)//插入j个乘号

                 for(int i=j+;i<=len;++i)//则最少有j+1位，枚举j+1~len位，此时插入j个乘号

                     for(int k=j;k<i;++k)//枚举j~i-1中的分断点k，找出最大的乘积作为dp[i][j]的值，即前i位加入j个乘号所能得到的最大乘积

                         dp[i][j]=max(dp[i][j],dp[k][j-]*num[k+][i]);

             cout<<dp[len][m-]<<endl;//表示前len位插入m-1个乘号

         }

     }

     return ;

 }