合并类len=2,[k]
消消乐类，len=3,[i+1][j-1]else [k]

Brackets

https://vjudge.net/problem/POJ-2955

#include<iostream>
#include<cstring>
using namespace std;

int dp[101][101];
bool flag=1;

bool pei(int i,int j,char a[]){
    if(a[i]=='('&&a[j]==')')return true;
    if(a[i]=='['&&a[j]==']')return true;

    return false;
}

void solu(){

char a[101];
scanf("%s",a+1);
if(a[1]=='e'){flag=0;return;}
int n=strlen(a)-1;


//不是连续，不是zuma类
//不是3个

//lcs类？

//zuma
for(int i=1;i<=n;i++)dp[i][i]=0;
for(int i=2;i<=n;i++)if(pei(i-1,i,a))dp[i-1][i]=2;

for(int len=3;len<=n;len++)
for(int i=1;i+len-1<=n;i++){
    int j=i+len-1;
    if(pei(i,j,a))dp[i][j]=max(dp[i][j],dp[i+1][j-1]+2);
    else for(int k=i;k<=j-1;k++){
        dp[i][j]=max(dp[i][j],dp[i][k]+dp[k+1][j]);
    }
}

cout<<dp[1][n];
//更是lis类
}
int main(){

while(flag){
    solu();
}



}