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，感觉是整个过程最完整的一道题。