[poj1742]coin

题意:多重背包的w=v特殊情况

分析:此题如果用单调队列O(nv)会被无耻卡常数……

然后鉴于此题W=V,所以只存在背包恰好为i的是否存在,即bool型的f[i]是否为1

即往背包染色上面考虑

如果是完全背包,那么有f[j]=f[j]|f[j-v[i]]

那么此题是不是不可以做呢?并不是,我们可以记录下每个状态所用的物品的个数,限制一下即可,不影响结果(因为这实际上不能算是dp,因为没有最优的抉择的选举,只是刷一遍)

教主果然吊……Orz StQ

原文地址:https://www.cnblogs.com/wmrv587/p/3627196.html