斜率优化 DP
当 Q_(i,j) 含 A(i)B(j) 时,把转移化为点与直线的截距,用下凸壳查询切线;按 X、K、窗口的单调性选择凸壳维护方式。时间 O(n) 至 O(n log^2 n),空间 O(n) · 标签 动态规划 / 斜率优化 / 凸壳 / DP 优化
问题形式
记 ,,,。考虑 1D/1D 动态规划中,当 时,方程退化为
其中 。把 看成截距,记 ,,,则
对固定的 ,每个候选 给出点 ; 是过 、斜率为 的直线的截距。转移就是求这些截距的最小值。
以下假设 。若 不单调,需要动态凸壳,不在本页范围。
核心思想
最小截距由 下凸壳上的点取得。把点按 递增插入,维护下凸壳:新点加入时,若最后三个点不再构成下凸,就删去中间的点。
查询斜率 时,在凸壳上找切线。若 单调,切点位置也单调,可以用指针移动;若 任意,则在凸壳上二分。
正确性
固定 ,表达式 对点 是线性的。下凸壳上方的点位于某条凸壳边的上方,其函数值不会小于该边某个端点的值;凸包内部的点可以写成凸壳顶点的凸组合,线性函数在凸组合上的值也不小于某个顶点。因此最小值一定在下凸壳上。
查询得到的切点截距就是 ,代回 的定义即得原转移。按 递增计算时,候选 已知,因此每一步都正确。
凸壳维护
设 单调递增。按 和窗口端点 的单调性,常见维护方式如下:
- 单调, 单调,:用单调队列维护凸壳,队首弹出已经不可能最优的点;均摊 。
- 任意, 单调,:用单调栈维护凸壳,查询时二分切点;。
- 任意,:维护可持久化凸壳,按 取对应的前缀版本;。
- 任意:线段树每个节点维护区间凸壳,查询拆成 段,每段二分;。
若 单调但大于 ,也可以在凸壳前端删除过期点;若 不单调,通常需要线段树凸壳。
易错点
- 斜率是 ,符号写反会把下凸壳用成上凸壳;取最大值时改用上凸壳。
- 插入点要求 单调; 相同时应保留 最小的点,否则凸壳会包含无效点。
- 不单调时不能弹队首,只能在凸壳上二分。
- 不单调时不能只维护当前凸壳,否则会用到尚未允许的决策。
- 时点会过期;普通的全局凸壳会保留已经失效的点。
- 凸壳的叉积比较用整数;用浮点斜率比较容易在共线或大坐标时出错。