[kuangbin带你飞]专题二十二 区间DP----POJ - 2955

#include<iostream>
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
int dp[505][505];
int main(){
  char s[1005];
  while(~scanf("%s",s+1)){
    if (!strcmp(s+1,"end"))break;
    int n=strlen(s+1);
    memset(dp,0,sizeof(dp));
    for (int len=1;len<=n;len++){
        for (int i=1;i+len-1<=n;i++){
            int j=i+len-1;
            if((s[i]=='(' && s[j]==')') || (s[i]=='[' && s[j]==']')){
                dp[i][j]=dp[i+1][j-1]+2;
            }
            for (int k=i;k<j;k++){
                dp[i][j]=max(dp[i][j],dp[i][k]+dp[k+1][j]);
            }
        }
    }
    printf("%d\n",dp[1][n]);
  }
  return 0;
}