题意分析

根据题目描述和我搜索到的资料，我们需要解决的问题是：给定一个括号序列，求其最长的正则括号子序列的长度。正则括号序列的定义如下：

1. 空序列是正则括号序列。
2. 如果 $s$ 是正则括号序列，则 $(s)$ 和 $[s]$ 也是正则括号序列。
3. 如果 $a$ 和 $b$ 都是正则括号序列，则 $ab$ 也是正则括号序列。
4. 没有其他序列是正则括号序列。

例如，以下序列是正则括号序列：

• $(), [], (()), ()[], ()[()]$ 而以下序列不是正则括号序列：
• $(, ], )(, ([)], [(]$

解题思路：

1. 动态规划法：我们可以使用动态规划来解决这个问题。定义一个二维数组 $dp[i][j]$，表示从索引 $i$ 到 $j$ 的子序列中，最长正则括号子序列的长度。
2. 状态转移方程：
   • 当 $s[i]$ 和 $s[j]$ 是匹配的括号（例如 $($ 和 $)$，或 $[$ 和 $]$），则 $dp[i][j] = dp[i+1][j-1] + 2$。
   • 否则，$dp[i][j] = \max(dp[i+1][j], dp[i][j-1])$。
3. 初始化：对于长度为 1 的子序列，$dp[i][i] = 0$；对于长度为 2 的子序列，如果匹配，则 $dp[i][i+1] = 2$，否则为 0。
4. 遍历顺序：从长度为 3 的子序列开始，逐步扩展到整个序列。

代码实现：

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#define MAXN 105
using namespace std;
char s[MAXN];
int dp[MAXN][MAXN];
bool check(int a,int b)
{
    if((a=='['&&b==']')||(a=='('&&b==')'))
        return true;
    return false;
}
int main()
{
    int i,j,k,len;
    while(gets(s))
    {
        memset(dp,0,sizeof(dp));
        if(s[0]=='e')
            break;
        len=strlen(s);
        for(i=0; i<len; ++i)
        {
            if(check(s[i],s[i+1]))
                dp[i][i+1]=2;
            else
                dp[i][i+1]=0;
        }
        for(int gap=3; gap<=len; ++gap)
            for(i=0; i+gap-1<len; ++i)
            {
                j=i+gap-1;
                if(check(s[i],s[j]))
                    dp[i][j]=dp[i+1][j-1]+2;
                for(k=i; k<j; ++k)
                    dp[i][j]=max(dp[i][j],dp[i][k]+dp[k+1][j]);
            }
        cout<<dp[0][len-1]<<endl;
    }
    return 0;
}