自动搬运

查看原文

来自洛谷，原作者为

	Kelin 这个家伙太菜，没什么可以留下的

搬运于2025-08-24 21:56:56，当前版本为作者最后更新于2018-01-24 08:41:18，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题意:求少了第i个物品,装满大小为j的背包的方案数$\mod10,n,m\le 2e3$

暴力显然是$O(n^2m)$做$n$次背包就好了

其实只要跑一次背包(全部物品都在)

然后我们考虑少了某个物品怎么办?

我们在01背包DP时会用到这个转移

for(int j=m;j>=w[i];--j)
    f[j]+=f[j-w[i]];

我们少了i物品就是在原来的基础上少了一次这样的转移

所以我们在原来的基础上顺推减去这样的一次转移就ok了

memcpy(g,f,sizeof f);
for(int j=w[i];j<=m;++j)
    g[j]-=g[j-w[i]];