题解 P4141 【消失之物】

· · 题解

题意:求少了第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]];