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