斜率优化 DP

当 Q_(i,j) 含 A(i)B(j) 时,把转移化为点与直线的截距,用下凸壳查询切线;按 X、K、窗口的单调性选择凸壳维护方式。

时间 O(n) 至 O(n log^2 n),空间 O(n) · 标签 动态规划 / 斜率优化 / 凸壳 / DP 优化

问题形式

记 𝑥𝑖=𝑥(𝑖),𝑦𝑗=𝑦(𝑗,𝑓(𝑗)),𝐴𝑖=𝐴(𝑖),𝐵𝑗=𝐵(𝑗)。考虑 1D/1D 动态规划中,当 𝑄𝑖,𝑗(𝑓(𝑗))=𝑥𝑖+𝑦𝑗+𝐴𝑖𝐵𝑗 时,方程退化为

𝑓(𝑖)=𝑥𝑖+min𝐿(𝑖)≤𝑗≤𝑅(𝑖){𝑦𝑗+𝐴𝑖𝐵𝑗}.

其中 1≤𝐿(𝑖)≤𝑅(𝑖)<𝑖。把 𝑓(𝑖)−𝑥𝑖 看成截距,记 𝑌𝑗=𝑦𝑗,𝑋𝑗=𝐵𝑗,𝐾𝑖=−𝐴𝑖,则

𝑓(𝑖)−𝑥𝑖=min𝐿(𝑖)≤𝑗≤𝑅(𝑖)(𝑌𝑗−𝐾𝑖𝑋𝑗).

对固定的 𝑖,每个候选 𝑗 给出点 𝑃𝑗=(𝑋𝑗,𝑌𝑗);𝑌𝑗−𝐾𝑖𝑋𝑗 是过 𝑃𝑗、斜率为 𝐾𝑖 的直线的截距。转移就是求这些截距的最小值。

以下假设 𝑋𝑗≤𝑋𝑗+1。若 𝑋 不单调,需要动态凸壳,不在本页范围。

核心思想

最小截距由 下凸壳上的点取得。把点按 𝑋 递增插入,维护下凸壳:新点加入时,若最后三个点不再构成下凸,就删去中间的点。

查询斜率 𝐾𝑖 时,在凸壳上找切线。若 𝐾𝑖 单调,切点位置也单调,可以用指针移动;若 𝐾𝑖 任意,则在凸壳上二分。

正确性

固定 𝑖,表达式 𝑌−𝐾𝑖𝑋 对点 (𝑋,𝑌) 是线性的。下凸壳上方的点位于某条凸壳边的上方,其函数值不会小于该边某个端点的值;凸包内部的点可以写成凸壳顶点的凸组合,线性函数在凸组合上的值也不小于某个顶点。因此最小值一定在下凸壳上。

查询得到的切点截距就是 min𝑗(𝑌𝑗−𝐾𝑖𝑋𝑗),代回 𝑓(𝑖) 的定义即得原转移。按 𝑖 递增计算时,候选 𝑓(𝑗) 已知,因此每一步都正确。

凸壳维护

设 𝑋𝑗 单调递增。按 𝐾𝑖 和窗口端点 𝑅(𝑖) 的单调性,常见维护方式如下:

  • 𝐾𝑖 单调,𝑅(𝑖) 单调,𝐿=1:用单调队列维护凸壳,队首弹出已经不可能最优的点;均摊 𝑂(𝑛)。
  • 𝐾𝑖 任意,𝑅(𝑖) 单调,𝐿=1:用单调栈维护凸壳,查询时二分切点;𝑂(𝑛log𝑛)。
  • 𝑅(𝑖) 任意,𝐿=1:维护可持久化凸壳,按 𝑅(𝑖) 取对应的前缀版本;𝑂(𝑛log𝑛)。
  • 𝐿(𝑖),𝑅(𝑖) 任意:线段树每个节点维护区间凸壳,查询拆成 𝑂(log𝑛) 段,每段二分;𝑂(𝑛log2𝑛)。

若 𝐿(𝑖) 单调但大于 1,也可以在凸壳前端删除过期点;若 𝐿(𝑖) 不单调,通常需要线段树凸壳。

易错点

  • 斜率是 𝐾𝑖=−𝐴(𝑖),符号写反会把下凸壳用成上凸壳;取最大值时改用上凸壳。
  • 插入点要求 𝑋𝑗 单调;𝑋 相同时应保留 𝑌 最小的点,否则凸壳会包含无效点。
  • 𝐾𝑖 不单调时不能弹队首,只能在凸壳上二分。
  • 𝑅(𝑖) 不单调时不能只维护当前凸壳,否则会用到尚未允许的决策。
  • 𝐿(𝑖)>1 时点会过期;普通的全局凸壳会保留已经失效的点。
  • 凸壳的叉积比较用整数;用浮点斜率比较容易在共线或大坐标时出错。
源码位置