CSP-S 2019 退役游记 && 破百纪念

现在时间 UTC+8 18:18 2019/11/15,距 CSP-S 2019 还有约 14 个小时。

是时候,准备离开机房了。

(刚好也是本 blog100 篇文章,顺便纪念一下www

 …

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

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

最近(两个月前)学习了斜率优化 —— 一种优化 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\) 组成的下凸壳上。

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