标签:DP 优化
8 个条目
-
概念 1D/1D 动态规划
状态数为 O(n)、每个状态有 O(n) 个决策的 DP 形式;给出无后效条件。
2026-11-15 -
概念 二分栈优化 DP
当 Q_(i,j) 可依赖 f(j)、最优决策满足决策单调性中的单交叉条件时,用二分栈在线维护决策区间,以 O(n log n) 求出全部 f(i)。
2026-11-13 -
概念 分治优化决策单调DP
当 Q_(i,j) (f(j))=w(i,j) 与 f(j) 无关且最优决策点满足决策单调性时,按中点扫描候选区间并递归,以 O(n log n) 求出全部 f(i)。
2026-11-13 -
概念 单调队列优化 DP
当可分离转移的决策窗口左右端点都单调时,用单调队列维护窗口内 y(j,f(j)) 的最小值,把每层转移降为均摊 O(1)。
2026-11-13 -
概念 单调队列优化多重背包
在多重背包模型上按重量余数分类,把每类转移化为长度至多 c_i+1 的滑动窗口最小值,用单调队列把 O(nmc) 降为 O(nm)。
2026-11-13 -
概念 前缀信息优化 DP
当转移只依赖前缀且 i、j 的贡献可分离时,维护 y(j,f(j)) 的前缀聚合,把 O(n^2) 的转移降为 O(n)。
2026-11-13 -
概念 线段树优化 DP
可分离转移的决策窗口任意时,用线段树维护 y(j,f(j)) 的区间最小值;若候选值随 i 区间加,则配合懒标记维护区间最值。
2026-11-13 -
概念 斜率优化 DP
当 Q_(i,j) 含 A(i)B(j) 时,把转移化为点与直线的截距,用下凸壳查询切线;按 X、K、窗口的单调性选择凸壳维护方式。
2026-11-13