[poj1742]coin时间:2023-03-09 18:36:51 题意:多重背包的w=v特殊情况 分析:此题如果用单调队列O(nv)会被无耻卡常数…… 然后鉴于此题W=V,所以只存在背包恰好为i的是否存在,即bool型的f[i]是否为1 即往背包染色上面考虑 如果是完全背包,那么有f[j]=f[j]|f[j-v[i]] 那么此题是不是不可以做呢?并不是,我们可以记录下每个状态所用的物品的个数,限制一下即可,不影响结果(因为这实际上不能算是dp,因为没有最优的抉择的选举,只是刷一遍) 教主果然吊……Orz StQ