BZOJ 4922: Karp-de-Chant Number – [贪心/背包DP]


题目传送门(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 
#include 
#include 
#include 
#include 
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原创, 转载必须以链接形式注明>原文链接<

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注