前段时间遇到个完全背包问题,于是看了DD牛的背包九讲，对于01背包和完全背包还好理解，不过对于多重背包我一直理解的不是很透彻，尤其是那个复杂度,我一直认为是O(N*V*Σ(log(n[i])))的，但是DD牛的九讲上说是O(V*Σ(log(n[i]))，这个复杂度确实是DD牛讲的那个,表示一开始我想错了。还有就是可以用单调队列优化达到O(N*V),于是上网搜了好多报告,无奈实在不懂。后来问了王向，他说不用单调队列也可以达到O(N*V)的,给了我个网址。昨天下午就学些了下。发现还比较好懂。今天上午就依着那个思路把1014和1742给写了，发现还可以速度不错。
附上1014的带注释代码