单调队列优化多重背包
在多重背包模型上按重量余数分类,把每类转移化为长度至多 c_i+1 的滑动窗口最小值,用单调队列把 O(nmc) 降为 O(nm)。时间 O(nm),空间 O(m) · 标签 动态规划 / 多重背包 / 单调队列 / DP 优化
问题形式
在 多重背包 模型中,固定第 种物品,转移为
其中约定 ()。直接枚举 需要 。下面固定物品和重量余数,把每个转移化为滑动窗口最小值。
余数类
固定物品 和余数 ,令
记 ,并令 。枚举 后,剩余重量为 ,所以
令 ,则 ,且
定义
得到
固定 后, 递增时窗口 只向右滑动,窗口长度至多为 。因此可以用单调队列维护 的最小值。
单调队列
对每个余数 单独扫描 :
- 把当前的 加入队尾,同时弹出队尾中 不小于它的下标。
- 弹出所有 的队首。
- 队首就是窗口最小值,代回 。
每个物品的所有余数类合计扫描 个容量,因此单层转移为 ,总时间为 。
用两行滚动数组保存上一层和当前层的 ,空间为 。
正确性
模型本身的正确性见 多重背包;这里验证余数类变换和单调队列没有改变转移。
固定 和 后,所有形如 的容量被同一余数类覆盖,不同余数类互不重叠。枚举 表示第 种物品选了 个,剩余重量 对应 。令 后,,把 从窗口中分离,窗口内的量正是 。因此上面的等式与原转移逐项对应。
窗口端点随 单调右移,单调队列始终保存窗口内未被支配的候选,队首就是最小值。代回后得到 ,所以每层转移正确;再按物品维归纳即可。
易错点
- 余数分类要求 ; 先按模型页的边界处理。
- 窗口长度至多为 ,对应 ;删除队首的条件是 。
- 必须使用上一层的 ;在原地滚动时要先保留旧行。
- 取最大值时把 换成 ,并相应改变单调队列的比较方向。
- 不同余数类的窗口互不相干,不能共用一个队列。
- 下标越界的位置要保持 ;否则会被当成合法转移。