标签:单调队列
2 个条目
-
概念 单调队列优化 DP
当可分离转移的决策窗口左右端点都单调时,用单调队列维护窗口内 y(j,f(j)) 的最小值,把每层转移降为均摊 O(1)。
2026-11-13 -
概念 单调队列优化多重背包
在多重背包模型上按重量余数分类,把每类转移化为长度至多 c_i+1 的滑动窗口最小值,用单调队列把 O(nmc) 降为 O(nm)。
2026-11-13
2 个条目
当可分离转移的决策窗口左右端点都单调时,用单调队列维护窗口内 y(j,f(j)) 的最小值,把每层转移降为均摊 O(1)。
在多重背包模型上按重量余数分类,把每类转移化为长度至多 c_i+1 的滑动窗口最小值,用单调队列把 O(nmc) 降为 O(nm)。