题目链接：http://poj.org/problem?id=2955
题目描述
我们定义一个字符串序列为“规则的括号序列”当且仅当它满足如下条件：
- 空字符串是规则的括号序列；
- 如果字符串 (s) 是一个规则的括号序列，那么 ((s)) 和 ([s]) 也是规则的括号序列；
- 如果字符串 (a) 和 (b) 都是规则的括号序列，那么 (ab) 也是规则的括号序列；
- 除此之外的字符串都不能称为规则的括号序列。
举个例子，下面的这些字符串都是规则的括号序列：
((), [], (()), ()[], ()[()])
与此同时，下面的这些字符串都不是规则的括号序列：
((, ], )(, ([)], ([(])
给你一个字符串 (a_1a_2...a_n)，你的任务是找到它的最长的一个满足“规则的括号序列”条件的子序列，并输出该最长规则括号子序列的长度。也就是说，你需要找到最长的一组下表(i_1,i_2,...,i_m) ，他们满足 (1 le i1 lt i2 lt ... lt im le n) ，同时 (a_{i_1}a_{i_2} ... a_{i_m}) 是规则的括号序列。
比如，给你一个字符串 (([([]])]) ，它的最长规则的括号子序列是 ([([])]) 。
输入格式
输入包含多组样例。每组样例占据一行，包含一个字符串，该字符串仅由 (() , $$ , ([) , (]) 组成。字符串的长度在 (1) 到 (100) 之间。
输入数据的最后一行包含一个字符串“end”用于标识文件结束。
输出格式
对于每一组数据（除了最后的“end”），你需要输出它的最长规则的括号子序列的长度。
样例输入
((()))
()()()
([]])
)[)(
([][][)
end
样例输出
6
6
4
0
6
题目分析
涉及的知识点：区间动态规划（区间DP）。
为了方便起见，我们这里将“最长规则的括号序列”简称为“目标序列”。
我们用 (dp[L][R]) 表示 字符串 (s) 的子串 (s[L..R]) ，那么：
- 首先我们要确定，如果字符串 (s) 是空串，或者它的长度为 (1) ，那么它的目标序列的长度肯定是 (0) ；
- 如果字符串 (s) 的长度为 (2) ， 那么当 (s=="()") 或者 (s=="[]") 的时候，它的目标序列的长度就是它本身的长度—— (2) ；否则，它的目标序列的长度为 (0) 。
- 当 (s[L]=='(') 并且 (s[R]==')') 或者 (s[L]=='[') 并且 (s[R]==']') 的时候， (dp[L][R]) 的一种备选方案（称为第 (1) 中备选方案）是 (dp[L+1][R-1] + 2) ；
- 不过 ((s')) 或者 ([s']) （这里 (s') 用于表示 (s[L+1 .. R-1]) 的目标序列）条件不一定是成立的，所以任何条件下都成立的一种备选方案（称为第2种备选方案）是 (max(dp[L+1][R], dp[L][R-1])) ，即我们剔除掉最左边的字符串，或者最右边的字符串所能够带来的效果；
- 还有一种情况是字符串 (s[L..R]) 是两个字符串拼接而成的，那么这种情况下，它的一种备选方案（称为第3种备选方案）是 (max(dp[L][i] + dp[i+1][R])) ，其中 (L+1 le i lt R-1) 。
然后我们发现还可以合并第2种备选方案到第3中备选方案中，因为 (max(dp[L+1][R], dp[L][R-1])) 其实就等于 (max(dp[L][i] + dp[i+1][R])) ，其中 (i=L) 或 (R-1) 。
所以第2及第3中备选方案合并到一起就是 (max(dp[L][i] + dp[i+1][R])) ，其中 (L le i lt R) 。
据此，我们可以编写代码如下：
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
const int maxn = 101;
int n, dp[maxn][maxn];
string s;
int main() {
while ((cin >> s) && s != "end") {
fill(dp[0], dp[0]+maxn*maxn, 0);
n = s.length();
for (int l = 2; l <= n; l ++) {
for (int i = 0; i+l-1 < n; i ++) {
int j = i + l - 1;
if (s[i] == '(' && s[j] == ')' || s[i] == '[' && s[j] == ']')
dp[i][j] = (l > 2 ? dp[i+1][j-1] : 0) + 2;
for (int k = i; k < j; k ++)
dp[i][j] = max(dp[i][j], dp[i][k] + dp[k+1][j]);
}
}
cout << dp[0][n-1] << endl;
}
return 0;
}