求括号的最大匹配数。
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <cstring> 5 #include <cmath> 6 #include <algorithm> 7 using namespace std; 8 9 bool match(char a, char b) 10 { 11 if(a=='[' && b== ']') 12 return true; 13 if(a=='(' && b==')') 14 return true; 15 return false; 16 } 17 int _max(int a, int b) 18 { 19 return a>b ? a:b; 20 } 21 int main() 22 { 23 char s[110]; 24 int i, j, k, g, len; 25 int d[110][110]; 26 while(cin>>s) 27 { 28 if(strcmp(s, "end")==0) 29 break; 30 len = strlen(s); 31 memset(d, 0, sizeof(d)); 32 for(i = 0; i < len-1; i++) 33 if(match(s[i], s[i+1])) 34 d[i][i+1] = 1; 35 36 for(k = 2; k < len; k++) //两个之间的距离 37 { 38 for(i = 0; i < len-k; i++) 39 { 40 j = i+k; 41 if(match(s[i], s[j])) 42 d[i][j] = d[i+1][j-1] + 1; 43 for(g = 0; g < k; g++) //把中间所有的断开相加，因为有大于整体的。 44 d[i][j] = _max(d[i][i+g]+d[i+g+1][j], d[i][j]); 45 } 46 } 47 cout<<2*d[0][len-1]<<endl; 48 } 49 return 0; 50 }