题目链接
1 #include <iostream>
2 #include <cstdio>
3 #include <cstring>
4 #include <vector>
5 #include <cmath>
6 #include <algorithm>
7 using namespace std;
8 int dp[101][101];
9 char str[101];
10 int judge(int x,int y)
11 {
12 if(str[x] == '['&&str[y] == ']')
13 return 1;
14 else if(str[x] == '('&&str[y] == ')')
15 return 1;
16 return 0;
17 }
18 int dfs(int L,int R)
19 {
20 int maxz,i;
21 maxz = 0;
22 if(dp[L][R] != -1)
23 return dp[L][R];
24 if(L >= R)
25 return 0;
26 if(judge(L,R))
27 maxz = max(maxz,2 + dfs(L+1,R-1));
28 for(i = L;i < R;i ++)
29 maxz = max(maxz,dfs(L,i)+dfs(i+1,R));
30 return dp[L][R] = maxz;
31 }
32 int main()
33 {
34 int len;
35 while(scanf("%s",str)!=EOF)
36 {
37 if(strcmp(str,"end") == 0)
38 break;
39 memset(dp,-1,sizeof(dp));
40 len = strlen(str);
41 printf("%d
",dfs(0,len-1));
42 }
43 return 0;
44 }