题目链接

http://poj.org/problem?id=2955

题目大意

我们定义一个字符串序列为“规则的括号序列”当且仅当它满足如下条件：
1、空字符串是规则的括号序列；
2、如果字符串 s 是一个规则的括号序列，那么 (s) 和 [s] 也是规则的括号序列；
3、如果字符串 a 和 b 都是规则的括号序列，那么 ab 也是规则的括号序列；
4、除此之外的字符串都不能称为规则的括号序列。
举个例子，下面的这些字符串都是规则的括号序列：
(), [], (()), ()[], ()[()]
与此同时，下面的这些字符串都不是规则的括号序列：
(, ], )(, ([)], ([(]
给你一个字符串 a1a2...an，你的任务是找到它的最长的一个满足“规则的括号序列”条件的子序列，并输出该最长规则括号子序列的长度。也就是说，你需要找到最长的一组下表i1,i2,...,im，他们满足1≤i1<i2<...<im≤n，同时ai1aid...aim是规则的括号序列。
比如，给你一个字符串 ([([]])] ，它的最长规则的括号子序列是 [([])]。
【输入格式】
输入包含多组样例。每组样例占据一行，包含一个字符串，该字符串仅由 (,),[,]组成。字符串的长度在1到100之间。
输入数据的最后一行包含一个字符串“end”用于标识文件结束。
【输出格式】
对于每一组数据（除了最后的“end”），你需要输出它的最长规则的括号子序列的长度。
【样例输入】
((()))
()()()
([]])
)[)(
([][][)
end
【样例输出】
6
6
4
0
6

解题思路

区间dp。
大佬说是板子题，我连板子都不会。
先枚举区间长度，再枚举区间左端点，计算区间右端点；
转移方程：
由匹配规则3可知，dp[L][R]=max(dp[L][R],dp[L][k]+dp[k+1][R])（dp[i][j]表示区间[i,j]最多匹配的个数）
由匹配规则2可知，当区间左端点与区间右端点匹配时，dp[L][R]=dp[L+1][R-1]+2
所以，当区间两端点匹配成功时，需要多计算个dp[L][R]=dp[L+1][R-1]+2
（可能还会想到 当左右端点不匹配时 dp[L][R]=max(dp[L+1][R],dp[L][R-1])，其实这只是第一个转移方程的特殊情况， k=L或R-1）

AC代码

#include<cstring>
#include<string>
#include<iostream>
#include<algorithm>
using namespace std;
const int N=110;
int dp[N][N],n;
string str;
bool judge(char ch1,char ch2){
    if(ch1=='(' && ch2==')') return true;
    if(ch1=='[' && ch2==']') return true;
    return false;
}
int main(){
    while(cin>>str&&str!="end"){
        memset(dp,0,sizeof dp);
        int n=str.size();
        str="."+str;
        for(int len=2;len<=n;len++)
            for(int L=1;L<n;L++){
                int R=L+len-1;
                if(R>n) break;
                if(judge(str[L],str[R])) dp[L][R]=dp[L+1][R-1]+2;    
                for(int M=L;M<R;M++) dp[L][R]=max(dp[L][R],dp[L][M]+dp[M+1][R]);
            }
        cout<<dp[1][n]<<endl;
    }
}