Description

Input

The input test file will contain multiple test cases. Each input test case consists of a single line containing only the characters (, ), [, and ]; each input test will have length between 1 and 100, inclusive. The end-of-file is marked by a line containing the word “end” and should not be processed.

Output

For each input case, the program should print the length of the longest possible regular brackets subsequence on a single line.

Sample Input

((())) ()()() ([]]) )[)( ([][][) end

Sample Output

6 6 4 0 6

1、只有一种括号的时候，可以用栈来存储：当栈不为空，且下一个符号为右半部分，此时就出栈。 2、有两种括号的话，如果是平衡的也可以用栈来做。但是如果不是平衡的就不成立，比如：([]]) 实际上是有4个符号是匹配的，但是如果用栈做的话，只会输出2。 3、从题目中的长度最大为100可以看出，这道题是用区间dp来做的，复杂度为$O(n^3)$ dp[i][j]表示区间 [i, j] 的最大括号个数，再枚举区间 [i, j] 所有的断点k，使区间所能分成的所有小区间，取最大值。

#include <cstdio> #include <iostream> #include <cstring> using namespace std; char s[105]; int dp[105][105]; int main(void) { while (scanf("%s", s + 1) != EOF && strcmp(s + 1, "end")){ memset(dp, 0, sizeof dp);//每次都要初始化 int n = strlen(s + 1); for (int len = 2; len <= n; len++){//区间长度 for (int i = 1; i <= n - len + 1; i++){//左端点 int j = i + len - 1;//右端点 if (s[i] == '(' && s[j] == ')' || s[i] == '[' && s[j] == ']')//看区间两端能否匹配上 dp[i][j] = dp[i + 1][j - 1] + 2; for (int k = i; k <= j - 1; k++)//枚举区间内的断点，找到最大值 dp[i][j] = max(dp[i][j], dp[i][k] + dp[k + 1][j]); } } printf("%d\n", dp[1][n]); } return 0; }