浅谈斜率优化——截距优化
最近(两个月前)学习了斜率优化 —— 一种优化 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 组成的下凸壳上。
那么现在只要维护这个下凸壳,每次在上面找点使得截距最小,拿来更新 …