提供一种和秦淮岸不一样的做法:
首先,由题意,连续的能匹配的括号序列就是 美观的
匹配括号序列,就不难想到用栈模拟。
一开始我的想法是,每次成功匹配就用i-s.top()+1更新答案。显然WA了,错误数据(的关键)是:
(){}
我只能输出2,而答案显然是4.
再看上面的话:连续的能匹配的括号序列就是 美观的
而这个做法显然没有考虑到连续。
然后我开一个f[i]表示以i为最右端点的最长美观的序列(如果不存在,则为0)。
用i-s.top()+1+f[s.top()-1]更新f[i]和答案(就是这一段的长度加上与s.top()相邻的)。
ps:下标要从1开始,因为从0开始时s.top()-1可能变成负数导致RE
代码有模板,直接看/**********/以后的内容
//Wan Hong 2.2
//home
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
#include<vector>
typedef long long ll;
typedef std::string str;
#define INF (1ll<<58)
ll read()
{
ll f=1,x=0;
char c=getchar();
while(c<'0'||c>'9')
{
if(c=='-')f=-1;
c=getchar();
}
while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();
return f*x;
}
ll max(ll a,ll b)
{
return a>b?a:b;
}
ll min(ll a,ll b)
{
return a<b?a:b;
}
bool umax(ll& a,ll b)
{
if(b>a)return a=b,1;
return 0;
}
bool umin(ll& a,ll b)
{
if(b<a)return a=b,1;
return 0;
}
/**********/
#include<stack>
#define MAXN 100011
char a[MAXN];
ll f[MAXN];
std::stack<ll>s;
ll turn(char a)//将括号转换成整数编号,并保证匹配的括号编号的和是0
{
if(a=='(')return -1;
if(a=='[')return -2;
if(a=='{')return -3;
if(a==')')return 1;
if(a==']')return 2;
if(a=='}')return 3;
return 0;
}
int main()
{
scanf("%s",a+1);
ll n=strlen(a+1),ans=0;
f[0]=0;
for(ll i=1;i<=n;++i)
{
ll now=turn(a[i]);
if(now<0)s.push(i);//左括号则入栈
else if(!s.empty()&&turn(a[s.top()])+now==0)//能匹配
{
f[i]=i-s.top()+1+f[s.top()-1];
umax(ans,f[i]);
s.pop();
}
else//不能匹配
{
while(!s.empty())s.pop();
f[i]=0;
}
}
printf("%lld",ans);
return 0;
}