单调队列/单调栈优化

[Ir1d]

https://oi-wiki.org/dp/optimizations/monotonous-queue-stack/

OI Wiki 是一个编程竞赛知识整合站点，提供有趣又实用的编程竞赛知识以及其他有帮助的内容，帮助广大编程竞赛爱好者更快更深入地学习编程竞赛

[IceySakura]

朴素多重背包复杂度有误，应为 $ O(W \sum k_i) $，而不应该再乘物品种类n

[Enter-tainer]

@SingerCoder hello~可以帮忙开一个 pr 修改一下吗

[noixcn]

介绍里面的将常数从max中提出来是否应该是f_{i,j} = max{f_{i-1,k} + b_i - |a_i - j|} = max{f_{i-1,k} - |a_i - j|} + b_i

[SYSU-Coder]

@noixcn
介绍里面的将常数从max中提出来是否应该是f_{i,j} = max{f_{i-1,k} + b_i - |a_i - j|} = max{f_{i-1,k} - |a_i - j|} + b_i

[SYSU-Coder]

这里的自变量是k

[ningago]

多重背包朴素算法时间复杂度为O(nm\sumk)吧

[cls1277]

@ningago
多重背包朴素算法时间复杂度为O(nm\sumk)吧

朴素算法的时间复杂度里应该没有$n$了，物品个数是$\sumk_i$了

[Kelatte]

orz，不过有没有单调栈优化的讲解呢？

[nRookie]

单调队列优化多重背包的第一个公式的后面的公式怎么推出来的？ 推了半天，没推出来

意思是j = y + xw吗？

有朋友帮忙解释一下不？

[laozhu1234]

看你写那么多式子也花了我不少时间,
你这样直接不断代入换元最后得到最后两个式子的理解方法也是可以理解的

是的,意思就是j=y+xw, 这里的单调队列优化是将mod x = y的所有j分为一组,跑一遍单调队列优化的dp, 对于y=0~x-1都跑一遍就将dp[i][j]全都求出来了.

[wxcbsd123]

有没有大佬来更新一下单调队列多重背包板块，状态设置太多了，让人思绪断断续续的，不易理解。