1 #include <cstdio> 2 #include <cstring> 3 #include <algorithm> 4 using namespace std; 5  6 char str[1000]; 7 int dp[1000][1000]; 8  9 int main()10 {11     while(scanf("%s",str)!=EOF)12     {13         if(!strcmp(str,"end")) break;14         int n=strlen(str);15         memset(dp,0,sizeof(dp));16         for(int i=n-2; i>=0; i--)17         {18             for(int j=i+1; j<n; j++)19             {20                 dp[i][j]=dp[i+1][j];21                 for(int k=i+1; k<=j; k++)22                 {23                     if((str[i]==‘(‘&&str[k]==‘)‘)||(str[i]==‘[‘&&str[k]==‘]‘))24                     {25                         dp[i][j]=max(dp[i][j],dp[i+1][k-1]+dp[k][j]+2);26                     }27                 }28             }29         }30         printf("%d\n",dp[0][n-1]);31     }32     return 0;33 }