首先将每个括号序列转化为三元组(ai,bi,ci),其中ai为左括号-右括号数量,bi为前缀最小左括号-右括号数,ci为序列长度。问题变为在满足Σai=0,bi+Σaj>=0 (j<i)的情况下,最大化Σci。
考虑在确定了选哪些序列的情况下如何排列能够尽量满足条件。显然应该把ai>0的放在前面,<0的放在后面。对于ai>=0,考虑按bi降序排列。因为假设这样排列后第一个不合法的位置是x,要让该位置合法显然应该将x后面的某个三元组i和前面的交换,但该三元组的bi<bx,且前面位置的Σaj更小,所以交换后仍不合法,所以这样不会更劣。对于ai<0就比较麻烦了,因为发现我们希望尽量按bi升序和按ai降序,但单独按其中一个排都能很容易的找到反例,所以我们按ai-bi降序排列。ai-bi的实际意义相当于后缀最大左括号-右括号数,添加过程中要求左括号数量始终不少于右括号。考虑反过来看,则要求右括号数量始终不少于左括号。由于ai<0,我们发现这个问题和之前的问题是相同的,只是左右括号反了过来,-(ai-bi)就相当于之前的bi。正确性就是这样了。
贪心顺序确定后,dp就很显然了,设f[i][j]为前i个括号序列左括号比右括号多j个时的答案即可。
果然检验出了我不会卡常数。为什么大家都跑的那么快啊。
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;
#define ll long long
#define N 310
char getc(){char c=getchar();while ((c<'A'||c>'Z')&&(c<'a'||c>'z')&&(c<''||c>'')) c=getchar();return c;}
int gcd(int n,int m){return m==?n:gcd(m,n%m);}
int read()
{
int x=,f=;char c=getchar();
while (c<''||c>'') {if (c=='-') f=-;c=getchar();}
while (c>=''&&c<='') x=(x<<)+(x<<)+(c^),c=getchar();
return x*f;
}
int n,m,q,f[N][N*N];
char s[N];
struct data{int x,y,z;
}a[N];
bool cmp(const data&a,const data&b)
{
return a.x>b.x;
}
bool cmp2(const data&a,const data&b)
{
return a.y>b.y;
}
bool cmp3(const data&a,const data&b)
{
return a.x-a.y>b.x-b.y;
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("bzoj4922.in","r",stdin);
freopen("bzoj4922.out","w",stdout);
const char LL[]="%I64d\n";
#else
const char LL[]="%lld\n";
#endif
n=read();
for (int i=;i<=n;i++)
{
scanf("%s",s+);a[i].z=strlen(s+);
for (int j=;j<=a[i].z;j++)
a[i].y=min(a[i].y,a[i].x+=(s[j]=='('?:-)),m+=s[j]=='('?:;
}
sort(a+,a+n+,cmp);int x=n+;
for (int i=;i<=n;i++) if (a[i].x<) {x=i;break;}
sort(a+,a+x,cmp2);sort(a+x,a+n+,cmp3);
memset(f,,sizeof(f));f[][]=;
for (int i=;i<=n;i++)
for (int j=;j<=m;j++)
{
f[i][j]=f[i-][j];
if (j-a[i].x>=&&j-a[i].x<=m&&j-a[i].x+a[i].y>=) f[i][j]=max(f[i-][j-a[i].x]+a[i].z,f[i][j]);
}
cout<<f[n][];
return ;
}