我们给出了正则括号序列的如下归纳定义： · 空序列是正则括号序列 · 如果s是正则方括号序列，那么(s)和[s]是正则方括号序列 · 如果a和b是正则括号序列，那么ab是正则括号序列 · 没有其它序列是正则括号序列 例如，以下所有字符序列都是正则方括号序列： () [] (()) ()[] ()[()] 而以下字符序列都不是： ( j ) 给定字符的方括号序列s，找到s的正则括号子序列的最大长度。
输入若干行字符串，以end为结尾
每行输出该字符串的最大正则子序列长度，end不输出
((())) ()()() ([]]) )[)( ([][][) end
6 6 4 0 6
很容易想到\(O(n)\)的假算法，即从左往右查询合法括号的总数量即可。但事实上，这种算法碰到这种情况会WA掉：\[([)]\] 因此，我们还是选择使用区间DP。每次查询到一组括号的两端分别在i和j时，使当前答案dp[i][j]=dp[i+1][j-1]+2，即该区间内的最大正则括号序列+2。我们再遍历i到j内的所有组合，取最大值即可。
#include<iostream> #include<cstdio> #define int long long #define maxn 1000 //#define local using namespace std; int n; string s; int dp[maxn][maxn]; inline void work(){ for(register int i=0;i<maxn;i++){ for(register int j=0;j<maxn;j++)dp[i][j]=0; } n=s.size(); int ans=0; for(register int i=n-1;i>=0;i--){ for(register int j=i+1;j<n;j++){ if(s[i]=='(' && s[j]==')' || s[i]=='[' && s[j]==']')dp[i][j]=dp[i+1][j-1]+2; for(int k=i; k<=j; k++)dp[i][j]=max(dp[i][j],dp[i][k]+dp[k][j]); } } cout<<dp[0][n-1]<<endl; } signed main(){ #ifdef local freopen("1.txt","r",stdin); #endif ios::sync_with_stdio(false); cin.tie(0); cin>>s; while(s!="end"){ work(); cin>>s; } return 0; }转载于:https://www.cnblogs.com/Chen574118090/p/11608602.html
