首页 > 其他 > 详细

[poj1742]coin

时间:2014-03-27 04:58:13      阅读:478      评论:0      收藏:0      [点我收藏+]

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

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

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

即往背包染色上面考虑

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

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

教主果然吊……Orz StQ

[poj1742]coin,布布扣,bubuko.com

[poj1742]coin

原文:http://www.cnblogs.com/wmrv587/p/3627196.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!