学步园

区间DP

dp[i][j] 表示从i -> j 满足题目要求的长度

如果i -> j 中位置k 满足 题目那俩种要求之一 就  +2 然后在+ dp[i][k-1] dp[k+1][j-1]

这些区间中的长度

#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
int const MAXN = 110;
char str[MAXN],s[MAXN];
int dp[MAXN][MAXN];
inline int Max(int a,int b){
    return a>b?a:b;
}
int main(){
    while(cin>>str){
        if(str[0] == 'e') break;
        int len = strlen(str);
        int cnt = 1;
        for(int i = 0;str[i];i++){
            s[cnt++] = str[i];
        }
        memset(dp,0,sizeof(dp));
        for(int l = 2;l <= len;l++){
            for(int i = 1;i <= len - l + 1;i++){
                int j = l + i - 1;
                for(int k = i;k < j;k++){
                    if(s[k] == '[' && s[j] ==']'){
                        dp[i][j] = Max(dp[i][j],dp[i][k - 1] + dp[k + 1][j - 1] + 2);
                    }
                    else if(s[k] == '(' && s[j] == ')'){
                        dp[i][j] = Max(dp[i][j],dp[i][k - 1] + dp[k + 1][j - 1] + 2);
                    }
                    else dp[i][j] = Max(dp[i][j],dp[i][j - 1]);
                }
                //cout<<i<<" "<<j<<" "<<dp[i][j]<<endl;
            }
        }
        printf("%d\n",dp[1][len]);
    }
    return 0;
}