括号匹配问题

· · 个人记录

【题目描述】： 


我们给出了“正则括号”序列的归纳定义：
空序列是一个正则括号序列，
如果S是一个正则括号序列，则（s）和[s]是正则括号序列，
如果A和B是正则括号序列，则AB是正则括号序列。
没有其他序列是正则括号序列。
例如，下列都是正则括号序列：
(), [], (()), ()[], ()[()] 而下列都不是：
(, ], )(, ([)], ([(] 给出一个的只有'(',')','[',']'四种括号组成的序列S，你的目标是找到最长的正则括号序列的长度，该序列是S的子序列。子序列即删除部分字符后余下的序列。
例如：给定初始序列([([]])]，最长正则括号子序列是[([])]。
【输入描述】：
包含多个测试用例。每个输入测试用例都只有'(',')','[',']'的单行组成；每个输入测试的长度在1到100之间，文件的结尾用包含“end”的一行标出，不应该被处理。
【输出描述】：
对于每个输入，程序应该在单行上打印最长可能的正则括号子序列的长度。
【样例输入】： 
((())) ()()() ([]]) )[)( ([][][) end 【样例输出】： 6 6 4 0 6 【时间限制、数据范围及描述】： 时间：1s 空间：64M

对于 30%的数据：字符串长度小于等于10；
对于100%的数据：字符串长度小于等于100；数据组数<=10

【解题思路】
区间DP
状态转移方程
dp[i][j]=dp[i+1][j-1]+2;
dp[i][j]=max(dp[i][j],dp[i][k]+dp[k][j])

【code】

```cpp
#include <cstdio>
#include <queue>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll; 
char s[105];
int f[105][105];
int main(){ 
    while(scanf("%s",s+1)){
        if(s[1]=='e')break; 
        int n=strlen(s+1); 
        memset(f,0,sizeof(f));
        for(register int l=2; l<=n; l++)
            for(register int i=1; i<=n; i++){ 
                int j=i+l-1;
                if(j>n) break; 
                if(s[i]=='('&&s[j]==')'||s[i]=='['&&s[j]==']') 
                    f[i][j]=f[i+1][j-1]+2; 
            for(register int k=i; k<j; k++) 
                f[i][j]=max(f[i][j],f[i][k]+f[k][j]); 
        } 
        printf("%d\n",f[1][n]); 
    }
 return 0; 
}

FINISHED