题解 P4141 【消失之物】
Kelin
2018-01-24 08:41:18
题意:求少了第i个物品,装满大小为j的背包的方案数$\mod10,n,m\le 2e3$
暴力显然是$O(n^2m)$做$n$次背包就好了
其实只要跑一次背包(全部物品都在)
然后我们考虑少了某个物品怎么办?
我们在01背包DP时会用到这个转移
```cpp
for(int j=m;j>=w[i];--j)
f[j]+=f[j-w[i]];
```
我们少了i物品就是在原来的基础上少了一次这样的转移
所以我们在原来的基础上顺推减去这样的一次转移就ok了
```cpp
memcpy(g,f,sizeof f);
for(int j=w[i];j<=m;++j)
g[j]-=g[j-w[i]];
```