斜率优化

· · 算法·理论

前言

芝士一个较为偏代数方面的斜率优化介绍。主要原因是较为懒得放图，凑活看吧（什么

虽然但是斜率优化并不是提高组考点，不过还是闲的没事写了介绍，是不是该祈祷考试时候可以拿来骗点分？

引入

在动态规划中，可能存在与 i,j 均相关的 dp，如：

dp_i=(\max/\min)\{A(i)+B(j)+C(i)D(j)\}

此时单调队列优化彻底尽力，需要使用斜率优化 qwq。

斜率优化

为了处理 \min() 的值，我们不得不充分发挥人类的智慧。

首先，我们考虑分别从 j_1,j_2 转移到 i，不妨设从 j_1 转移到 i 更优，那么有：

A(i)+B(j_1)+C(i)D(j_1)<A(i)+B(j_2)+C(i)D(j_2)

为了方便后面递推，我们将 i 放到一边，得：

\dfrac{B(j_1)-B(j_2)}{D(j_1)-D(j_2)}<-C(i)

注意到，左边的柿子形如求坐标系中连接两个点的直线的斜率的柿子 k=\dfrac{y_1-y_2}{x_1-x_2}，于是我们把它转移到坐标系中，就有了：

P_1=(D(j_1),B(j_1)) \\ P_2=(D(j_2),B(j_2))

把这个柿子拓展一下，对于任意一种可转移过来的状态 j，我们把它看作坐标系中的一个点 (D(j),B(j))，再对于任意两种状态进行比较（也就是求他们的斜率是否小于 -C(i)），就可以得到最优转移策略。

然而这还是 O(n) 得 qwq。。
所以我们需要将其继续优化。

考虑三种状态 j_1<j_2<j_3，显然，i 可能从 j_2 转移过来，当且仅当满足 k_{j_1,j_2}\leq-C(i)\leq k_{j_2,j_3}，满足斜率单调，所以说 j_2 必须在所有点的下凸包上。因此，我们只需要维护凸包，再从凸包上选取最优点就可以了。

现在再考虑凸包上最优点，因为凸包上的斜率具有单调性，所以可以二分寻找第一个斜率满足小于 -C(i) 的线段，此时不难发现两侧的点均不优于这条线段左侧的点，所以只需二分查找这条线段即可。

求 \max() 的情况与此类似。

接下来我们考虑实现 qwq。

一般的斜率优化题，可以分为以下四种：

  1. 横坐标单调，斜率单调
  2. 横坐标单调，斜率不单调
  3. 横坐标不单调，斜率单调
  4. 横坐标不单调，斜率不单调

我们分别有不同的处理方法。

（注：借鉴了这篇文章的分类标准，加了一点实现方法）

1. 横坐标单调，斜率单调

考虑凸包的单调性和斜率的单调性是否相同，绝大多数可直接使用 vector 之类的线性数据结构维护，每次加入一个新点，每次更新把队首不符合斜率要求的元素弹出。

修改复杂度：O(1)
查询复杂度：O(1)

2. 横坐标单调，斜率不单调

使用单调队列维护。

保证队列内斜率单调，每次加入新点时若队列末尾两个点到新点的斜率不符合单调性，则将队尾弹出，查询使用二分查找。

修改复杂度：O(1)（总复杂度 O(n) 均摊）
查询复杂度：O(\log n)

3. 横坐标不单调，斜率单调

使用链表或 set 维护。

保证链表或 set 内斜率单调且按 x 坐标排序，加入新点时，二分查找横坐标对应位置，随后向两边拓展，将不符合单调性的点弹出，查询使用二分查找。

修改复杂度：O(\log n)（总复杂度 O(n+q \log n) 均摊）
查询复杂度：O(\log n)

4. 横坐标不单调，斜率不单调

使用李超线段树，cdq分治或平衡树维护。

需要支持以下操作：

  1. 插入一个点 (x,y)；
  2. 删除一个点；
  3. 查询按 x 坐标排序时，(x,y) 的上/下一个下标；
  4. 查询按 x 坐标排序时，第一个满足 k_{i-1,i}\leq -C(i) \leq k_{i,i+1} 的 i。

修改复杂度：O(\log n)
查询复杂度：O(\log n)

例子

以 P3195 [HNOI2008] 玩具装箱 为例：

读题，容易想到令 dp_i 代表选完第 i 个物品时的最小代价。

则答案为 dp_n，状态转移方程为：

dp_i=\min\{dp_j+(i-(j+1)+\sum\limits^{i}_{k=j+1}C_k-L)^2\}

用前缀和化简，令 \sum\limits^{x}_{k=1}C_k=S_x，则有：

\begin{aligned} dp_i &=\min\{dp_j+(i-(j+1)+S_i-S_j-L)^2\} \\ &=\min\{dp_j+(S_i+i-S_j-j-1-L)^2\} \\ \end{aligned}

可以将 S_x 和 x 合并，令 S'_x=x+\sum\limits^{x}_{k=1}C_k 。

即 S'_x=\sum\limits^{x}_{k=1}(C_k+1)，仍可用前缀和维护。

可以将 L 和 1 合并，令 L'=L+1，则有：

dp_i=\min\{dp_j+(S'_i-S'_j-L')^2\}

展开，得：

dp_i=\min\{dp_j+S'^2_j+2S'_j(L'-S'_i)\}+(S'_i-L')^2

对应到一般公式，有：

\begin{aligned} A(i)&=(S'_i-L)^2 \\ B(j)&=dp_j+S'^2_j \\ C(i)&=2(L'-S'_i) \\ D(j)&=S'_j \end{aligned}

故将每个状态 j 看作平面上的点 (D(j),B(j))，维护平面上所有点的下凸包，每次二分查找凸包上第一个斜率小于 -C(i) 的线段，左端点即为最优点。

容易发现其为横坐标单增，斜率也单增的斜率优化 dp，使用单调队列维护凸包然后二分查找就可以勒。

更新日志

update 2024.7.10 : 开工
update 2024.7.11 : 没写完
update 2024.7.12 : 依旧没写完（
update 2024.9.16 : 仍然没写完
update 2024.11.8 : 终于写完乐（流出感动泪水
update 2024.11.10 : 审核打回重写 qwq
update 2024.11.25 : 二次打回 qwq update 2025.7.20 : 疑似有误重改