标签:决策单调性
3 个条目
-
概念 二分栈优化 DP
当 Q_(i,j) 可依赖 f(j)、最优决策满足决策单调性中的单交叉条件时,用二分栈在线维护决策区间,以 O(n log n) 求出全部 f(i)。
2026-11-13 -
概念 决策单调性
最优决策点 J(i) 随 i 单调;每个决策的最优位置连续。单交叉是更强的两两比较条件。
2026-11-13 -
概念 分治优化决策单调DP
当 Q_(i,j) (f(j))=w(i,j) 与 f(j) 无关且最优决策点满足决策单调性时,按中点扫描候选区间并递归,以 O(n log n) 求出全部 f(i)。
2026-11-13