题意：给你n个括号序列，让你尽量选出多的括号序列，使得最终的总序列加起来刚好为一个合法序列。
套路大集合 算出每个括号序列的前缀和，然后就是bzoj3709： y>x的和y
#include<iostream> #include<cstring> #include<cmath> #include<algorithm> #include<cstdlib> #include<cstdio> using namespace std; #define N 310 #define MAXM 1010 #define ll long long #define INF 1000000000 struct node{ int x,y,len; }a[N],b[N]; int n; char s[N]; int f[N][N*N]; int tot1,tot2; int ans; bool cmp1(const node &x,const node &y){ return x.x<y.x; } bool cmp2(const node &x,const node &y){ return x.x+x.y>y.x+y.y; } int main() { int i,j; scanf("%d",&n); for(i=1;i<=n;i++) { scanf("%s",s+1); a[i].x=0; int now=0; for(j=1;s[j];j++){ now+=s[j]=='('?1:-1; a[i].x=max(a[i].x,-now); } //printf("%d\n",now); a[i].len=j-1; a[i].y=now; } for(i=1;i<=n;i++) { if(a[i].y>=0) a[++tot1]=a[i]; else b[++tot2]=a[i]; } if(tot1) sort(a+1,a+tot1+1,cmp1); if(tot2) sort(b+1,b+tot2+1,cmp2); memset(f,0xef,sizeof(f)); f[0][0]=0; for(i=1;i<=tot2;i++) a[tot1+i]=b[i]; int s=0; for(i=1;i<=n;i++){ for(j=0;j<=s;j++){ f[i][j]=f[i-1][j]; } for(j=a[i].x;j<=s;j++){ f[i][j+a[i].y]=max(f[i][j+a[i].y],f[i-1][j]+a[i].len); } s+=a[i].len; } printf("%d\n",f[n][0]); return 0; }