【题目描述】：

我们给出了“正则括号”序列的归纳定义：

空序列是一个正则括号序列，

如果S是一个正则括号序列，则（s）和[s]是正则括号序列，

如果A和B是正则括号序列，则AB是正则括号序列。

没有其他序列是正则括号序列。

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

(),[],(()),()[],()[()] 而下列都不是：

(,],)(,([)],([(] 给出一个的只有‘(‘,‘)‘,‘[‘,‘]‘四种括号组成的序列S，你的目标是找到最长的正则括号序列的长度，该序列是S的子序列。子序列即删除部分字符后余下的序列。

例如：给定初始序列([([]])]，最长正则括号子序列是[([])]。

【输入描述】：

包含多个测试用例。每个输入测试用例都只有‘(‘,‘]‘的单行组成；每个输入测试的长度在1到100之间，文件的结尾用包含“end”的一行标出，不应该被处理。

【输出描述】：

对于每个输入，程序应该在单行上打印最长可能的正则括号子序列的长度。

【样例输入】：

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

【样例输出】：

6 6 4 0 6

【时间限制、数据范围及描述】：

时间：1s 空间：64M

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

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

代码

#include<algorithm> #include<iostream> #include<cstring> #include<queue> #include<cmath> #include<cstdio> using namespace std; int a[101][101]; char s[101]; int main(){ while(scanf("%sn",s+1)==1 && s[1]!=‘e‘){ int len=strlen(s+1); memset(a,0,sizeof(a)); for(int i=len-1;i>=1;i--){ for(int j=i+1;j<=len;j++){ a[i][j]=a[i+1][j]; for(int k=i+1;k<=j;k++){ if(s[i]==‘(‘&&s[k]==‘)‘ || s[i]==‘[‘ && s[k]==‘]‘){ a[i][j]=max(a[i][j],a[i+1][k-1]+a[k+1][j]+2); } } } } printf("%dn",a[1][len]); } return 0; } 

读取有些小问题，后修复。