1 //Accepted    200 KB    63 ms 2 //区间dp 3 //dp[i][j] 从i位到j位能得到的最大匹配数 4 //dp[i][j]=max(dp[i+1][j-1] (s[i-1]==s[j-1]),dp[i][k]+dp[k+1][j])i<=k<j 5 #include <cstdio> 6 #include <cstring> 7 #include <iostream> 8 using namespace std; 9 const int imax_n = 105;10 int dp[imax_n][imax_n];11 char s[imax_n];12 int n;13 int max(int a,int b)14 {15     return a>b?a:b;16 }17 int isMatch(char ch1,char ch2)18 {19     if (ch1==‘(‘ && ch2==‘)‘) return 1;20     if (ch1==‘[‘ && ch2==‘]‘) return 1;21     return 0;22 }23 void Dp()24 {25     for (int i=1;i<=n;i++)26     dp[i][i]=0;27     for (int l=2;l<=n;l++)28     {29         for (int i=1;i<=n;i++)30         {31             int j=i+l-1;32             if (j>n) break;33             dp[i][j]=0;34             if (isMatch(s[i-1],s[j-1])) dp[i][j]=dp[i+1][j-1]+2;35             for (int k=i;k<j;k++)36             dp[i][j]=max(dp[i][j],dp[i][k]+dp[k+1][j]);37         }38     }39     printf("%d\n",dp[1][n]);40 }41 int main()42 {43     while (scanf("%s",s) && s[0]!=‘e‘)44     {45         n=strlen(s);46         Dp();47     }48     return 0;49 }