1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <algorithm> 5 #define pf(x) printf("%d ", x) 6 #define CL(x, y) memset(x, y, sizeof(x)) 7 #define max(a, b) (a > b ? a : b) 8 using namespace std; 9 const int MAX = 105; 10 char str[105]; 11 int length, dp[MAX][MAX]; 12 bool match(char i, char j); 13 int main() 14 { 15 while(gets(str) && strcmp(str, "end")) 16 { 17 int i, j, k, m; 18 length = strlen(str); 19 CL(dp, 0); 20 for(i = 0; i < length; i++) 21 { 22 if(match(str[i], str[i+1])) 23 dp[i][i+1] = 1; 24 } 25 for(k = 2; k < length; k++) 26 for(i = 0; i < length-k; i++) 27 { 28 j = i+k; 29 if(match(str[i], str[j])) 30 dp[i][j] = dp[i+1][j-1]+1; 31 for(m = 0; m < k; m++) 32 dp[i][j] = max(dp[i][j], dp[i][i+m] + dp[i+m+1][j]); 33 } 34 pf(dp[0][length-1]*2); 35 } 36 return 0; 37 } 38 bool match(char i, char j) 39 { 40 if(i=='(' && j==')') 41 return true; 42 if(i=='[' && j==']') 43 return true; 44 else 45 return false; 46 } 47 // gets(str) 包括空格 48 // cin 则不存在 49 // string str; str.size()代表长度 50 // const int maxn = 110;