题目传送门(BZOJ)

题解 :

首先请看一下这道题的贪心
其实本题同样也是类似 3709/4619 的一个形式, 不过由于直接选所有的不一定合法, 故需要加上可行性验证
对于每个序列, 我们只需要记录三个东西 : 多出来多少 '('(可以是负值, 表示少), 需要前面补多少 '(', 序列长度
第一个可以直接对左右括号赋值 1 和 -1, 对读入直接求和即可
第二个是第一个求和过程中, 绝对值最大的负值, 因为后面的左括号是不能匹配之前的的右括号的
按之前的贪心思路, 加一个背包求出最大答案即可

状态 :

F[i][j] 表示选择到第 i 个序列 (排好序之后), 还能给后面补 j'(' 的最大长度

转移 :

设之前那三个量分别为 x, y, z
F[i][j+y_i] = \max(F[i][j+y_i], F[i-1][j]+z_i)
j+y_i \ge 0 时可以转移, 由于一个序列可以不选, 所以注意从 i-1 先复制一遍状态
初始值 F[0][0] = 0

代码 :

#include <queue>#include <cstdio>#include <cstring>#include <iostream>#include <algorithm>using namespace std;const int N = 310;struct PART { int x, y, z; // x : Need y : Last z : len bool operator < (const PART &A) const { if((y > 0) != (A.y > 0)) return (y > 0) > (A.y>0); if( y > 0) return x < A.x; return x+y > A.x+A.y; }}a[N];char s[N];int f[N][N*N];int main() { int n, m = 0; scanf("%d", &n); for(int i = 1; i <= n; i ++ ) { scanf("%s", s+1); a[i].z = strlen(s+1); m += a[i].z; for(int j = 1; j <= a[i].z; j ++ ) { a[i].y += s[j] == '(' ? 1 : -1; a[i].x = max(a[i].x, -a[i].y); } } sort(a+1, a+n+1); memset(f, 0xc0, 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]; for(int 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;}

本文为Yirannn原创, 转载必须以链接形式注明>原文链接<