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 
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原创, 转载必须以链接形式注明>原文链接<

发表评论

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