首先将每个括号序列转化为三元组(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<'0'||c>'9')) c=getchar();return c;} int gcd(int n,int m){return m==0?n:gcd(m,n%m);} int read() { int x=0,f=1;char c=getchar(); while (c<'0'||c>'9') {if (c=='-') f=-1;c=getchar();} while (c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),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 "; #else const char LL[]="%lld "; #endif n=read(); for (int i=1;i<=n;i++) { scanf("%s",s+1);a[i].z=strlen(s+1); for (int j=1;j<=a[i].z;j++) a[i].y=min(a[i].y,a[i].x+=(s[j]=='('?1:-1)),m+=s[j]=='('?1:0; } sort(a+1,a+n+1,cmp);int x=n+1; for (int i=1;i<=n;i++) if (a[i].x<0) {x=i;break;} sort(a+1,a+x,cmp2);sort(a+x,a+n+1,cmp3); memset(f,200,sizeof(f));f[0][0]=0; for (int i=1;i<=n;i++) for (int j=0;j<=m;j++) { f[i][j]=f[i-1][j]; if (j-a[i].x>=0&&j-a[i].x<=m&&j-a[i].x+a[i].y>=0) f[i][j]=max(f[i-1][j-a[i].x]+a[i].z,f[i][j]); } cout<<f[n][0]; return 0; }