code:
#include <bits/stdc++.h> #define N 310 using namespace std; void setIO(string s) { string in=s+".in"; string out=s+".out"; freopen(in.c_str(),"r",stdin); // freopen(out.c_str(),"w",stdout); } struct node { int x,y,z; bool operator<(const node a) const { if(y>0&&a.y<=0) return 1; if(y<0&&a.y>=0) return 0; if(y>0) return x<a.x; return x+y>a.x+a.y; } }a[N]; int f[N][N*N]; char str[N]; int main() { // setIO("input"); int n,m=0,i,j; scanf("%d",&n); for(i=1;i<=n;++i) { scanf("%s",str); a[i].z=strlen(str),m+=a[i].z; for(j=0;j<a[i].z;++j) { a[i].y+=(str[j]=='('?1:-1),a[i].x=max(a[i].x,-a[i].y); } } sort(a+1,a+1+n); // for(j=0;j<=m;++j) f[0][j]=-1000000000; memset(f[0],0xc0,sizeof(f[0])); f[0][0]=0; for(i=1;i<=n;++i) { for(j=0;j<=m;++j) f[i][j]=f[i-1][j]; for(j=a[i].x;j<=m;++j) if(j+a[i].y>=0&&j+a[i].y<=m) f[i][j+a[i].y]=max(f[i][j+a[i].y],f[i-1][j]+a[i].z); } printf("%d\n",f[n][0]); return 0; }
