浅谈斜率优化——截距优化

最近（两个月前）学习了斜率优化 —— 一种优化 1D1D 动态规划转移方程的高效方法，在较高难度的比赛中是一种十分常见的 DP 优化手段。鉴于我之前（一年前）也稍微接触过一点相关方面的知识，但是完全没有搞懂（太菜了），最近（两个月前）再配合 orzCJK学长 提出的截距优化的思想理念才对于斜率优化问题有了深刻的见解，故在这里对 orzCJK学长 的 斜率优化_截距优化！.pdf 进行详细的解释说明。

首先，1D1D 指的是状态数 \(O(n)\) 转移 \(O(n)\) 的动态规划方程。在满足一些条件的情况下，斜率优化可以将转移的 \(O(n)\) 优化至 \(O(logn)\) 甚至可以到 \(O(1)\) 。这样时间复杂度就由 \(O(n^2)\) 变为 \(O(nlogn)\) 甚至是 \(O(n)\) ，可见斜率优化的高效性。

如果有一个 DP 方程的某个状态为 \(f_i\) ，如果能推导出类似于 \(f_i=c_i + \min\limits_{j<i \land \cdots}{\{a_j + w_i \cdot b_j\}}\) ，那么这个转移方程就可以使用斜率优化进行优化。

然而普通的转移方程并没有什么特殊的地方，使用经典的方法（我也不会）略显繁琐，所以现在我们要赋予它以几何意义。（时刻注意，这个转移方程的意义是对于一个 \(i\) 在 \(j < i\) 范围内寻找 \(j\) 使 \(a_j + w_i \cdot b_j\)）最小。）

换一下变量名，设 \(y_j=a_j, k_i=-w_i, x_j=b_j\) ，那么这样需要最小化的式子就变为 \(\underbrace{a_j}_{y_j} – \underbrace{-w_i}_{k_i} \cdot \underbrace{b_j}_{x_j}\) 。这不就是截距 \(b = y – kx\) 吗？！！也就是说，要最小化的就是一条过 \(\left(x_j, y_j\right)\) 且斜率为 \(k_i\) 的直线的截距！

换句话说，把所有对于当前 \(i\) 可转移的 \(j\) 都表示为二维平面上的一个点 \(p_j=\left(x_j, y_j\right)\) ，我们需要做的就是在所有这样的点中，找到一个点，使经过它且斜率为 \(k_i\) 的直线的截距最小！这也是为什么斜率优化就是截距优化的原因，它其实优化的是截距！

现在想象一条斜率固定的直线从下往上平移，当它第一次经过某个点 \(p_j\) 时，这时的截距肯定取到最小值。那么这个点 \(p_j\) 在什么地方呢？显然，它会在所有 \(p\) 组成的下凸壳上。

那么现在只要维护这个下凸壳，每次在上面找点使得截距最小，拿来更新 …