BZOJ 2287: [POJ Challeng]消失之物 – [DP]


题目传送门(BZOJ)

题解 :

这题大师讲的很明白辣, 我觉得我只是复述了一遍…
不包含物品 $i$ 的方案就是所有方案 – 包含 $i$ 的方案
就是 $G[i] = F[j] – F[j-w[i]]$ (G[] 省略了第二维, F[] 省略了第一维, 理解一下就好)
但是 $j-w[i]$ 这部分还可能有包含 $i$ 的方案,
所以要把多减的加回来 : $G[i] = F[j]-F[j-w[i]]+F[j-2\times w[i]]-…$
实际上就是 $G[i][j] = F[i][j]-G[i][j-w[i]]$
第一维是必须省略掉的, 因为在不考虑物品 $i$ 时是需要考虑 $i$ 之后的所有物品的

代码 :

#include <cstdio>
int f[2100], g[2100], w[2100];
int main() {
    int n, m; scanf("%d%d", &n, &m);
    f[0] = 1;
    for(int i = 1; i <= n; i ++ ) {
        scanf("%d", &w[i]);
        for(int j = m; j >= w[i]; j -- ) (f[j] += f[j-w[i]]) %= 10;
    }
    for(int i = 1; i <= n; i ++ ) {
        for(int j = 0; j < w[i]; j ++ ) g[j] = f[j];
        for(int j = w[i]; j <=m; j ++ ) g[j] = (f[j]-g[j-w[i]]+10)%10;
        for(int j = 1; j <= m; j ++ ) printf("%d", g[j]);
        putchar('\n'); 
    }
}

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

发表评论

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