slope trick 小记

有趣的问题 · 2023-03-26 10:17:56 · 个人记录

学习的过程比较艰辛，搞了半天才搞明白，所以记录一下。

适用范围

优化形如 f_{i,j}=|x_i-j|+\min f_{i-1,k} 的 DP 转移。

原理

由于绝对值函数是连续，下凸的一次函数，因此几个绝对值函数相加仍然满足这一特点，即归纳证明将 DP 式子的第二维当做横坐标后，每个 f_i 的图像也满足这一特点。我们考虑存储每次斜率 +1 的横坐标，从而快速转移 DP。

解题方法

首先尝试列出朴素的 n^2 DP式子，如最开始的例子。然后考虑 k 的取值范围。假设每次转移中 k 的取值范围是 [l_i,r_i]，则整个函数有以下变化：

• 最低点右边的部分全部向右平移 r_i-l_i，最低点的范围增加 r_i-l_i。

• 在 x_i 这个点，斜率增加了 2，即维护的点集需要增加两个 x_i。

• 若当前 x_i 在最低点左边，则左边下降的部分的最后一段变成上升的，反之亦然。

由这 3 条关键信息，我们可以用堆来维护点集。比较好的例子是 CF1534G，感觉是整个过程最完整的一道题。