slope trick 小记

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

适用范围

优化形如 \(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，感觉是整个过程最完整的一道题。