斜率优化总结

· · 个人记录

前言

本文宗旨解释一下斜率优化本质问题，而不是表面上的讲解一个模板，本文可以作为一个较为权威的资料参考学习，但不建议直接使用本材料第一次学习斜率优化，这样只是知识的灌输，而没有思考。

前置知识

  1. DP
  2. 平面直角坐标系
  3. 直线解析式
  4. 凸包

递增指的是，对于一个序列任 S 有： s_i,s_j\forall S \cup i < j,s_i \leq s_j ；同理定义递减 s_i,s_j\forall S \cup i < j,s_i \geq s_j 。

在本文中，凸多边形是指所有内角大小都在 \left[0,\pi\right] 范围内的简单多边形。

下凸壳就是对于按照x轴排序的的点，前一个点和后一个点的直线斜率从 \left[-\infty,\infty\right] 单调递增。

上凸壳就是对于按照x轴排序的的点，前一个点和后一个点的直线斜率从 \left[\infty,-\infty\right] 单调递增。

一条直线对于 X 轴的截距指的是其常数项的大小(可能为负) 。

正文

斜率优化适用范围

斜率优化dp，这个dp自然需要转移方程，将这个dp转移方程化为一个多项式形式，那么只有满足这样的多项式转移方程才能适用斜率优化：

dp_i=\min_{j\in set_i}\left(Y_j+K_i\times X_j+B_i\right)

或者

dp_i=\max_{j\in set_i}\left(Y_j+K_i\times X_j+B_i\right)

这里我们先看 \min 的情况。这个式子在求解 i 这个状态的答案，而 j 相当于在能对 dp_i 贡献的状态中进行枚举，对于其中 Y_j,K_i,B_i 三个函数，分别只与其自变量相关，即只与 j,i,i 相关，并且已知 K_i,B_i ，这时找到一个 j 使其和最小即可转移。

这个程序的时间复杂度容易分析 \mathcal{O}\left(\sum_{i=1}^{n}|set_i|\right) ，其中n并不一定是所有的状态数，由于dp本质是DAG，那么我们对于这个包含最终答案的联通块进行拓扑排序，形成一个求解顺序，n就是最少可以求解的状态数量。

对于这个式子考虑对于每一次求解进行优化，期望可以得到 \mathcal{O}\left(1\right) \text{ or } \mathcal{O}\left(\log|set_i|\right) 的世间复杂度，那么总体时间复杂度就会减小很多，极其接近于 \mathcal{O}\left(n\right) 的时间复杂度。

考虑可以对这个式子进行移项：

dp_i-K_i\times X_j-B_i=Y_j

这个式子的每一组取值就是关于这个状态的一种转移方式，所以我们舍去 \min 来看，但是这样看着麻烦，重新定义一下 K_i,B_i 写成这样：

K_i\times X_j+B_i+dp_i=Y_j

发现这个式子可以看成一个直线解析式，其中已知了斜率 k ，并且 B_i+dp_i 一起作为了这条直线和y轴的截距，而不是只是 B_i ，而且由于这个dp式子要有意义，也就是要是一个真实存在的一个转移，那么 X_j 和 Y_j 必须是一个存在的值才行，考虑在考查每一个 j 的时候，就已知了 X_j 和 Y_j ，把 \left(X_j,Y_j\right) 看做一个点，相当于这条直线过了这个点，即可解出 dp_i ，要使得 dp_i 尽量小，而 B_i 在求解这个状态中始终不变，那么要使这个直线和y轴的截距就要尽量小。那么这条这时问题就变成，找到一个点，使得这条直线截距(这里的)最小。

举个例子，对于下图这些点，随机取几个斜率范围在 \left[-\infty,\infty\right] ，并且求解到最小值，能取到的点像这样：

实际上维护的就是一个下凸壳，显然其他的点都是没用的，下图是要维护的点集：

同理如果是 \max 则是维护上凸壳。

特殊斜率优化

大多数情况中我们都是在顺序求解 dp_i ，对于解集也是顺序插入每一个 j ，而不是在一个DAG中使用拓扑排序顺序求解。

X 和 Y 均有单调性 / 线性数据结构维护

队列情况：

||斜率递增|斜率递减| |--|--|--| |X递增|min/维护下凸壳|max/维护上凸壳| |X递减|max/维护上凸壳|min/维护下凸壳|

这些情况下都可以使用单调队列维护。以斜率递增并且 X 递增的情况来说。

对于每次放入一个点到点集的时候，将其放入对头，但是这样可能破坏下凸壳性质，所以要一直从对头弹出点，直到符合下凸壳性质，显然这些弹出的点以后永远不会成为更优解；

例如下图，加入了橙色点，橙点和紫点的直线斜率小于黑点和紫点的直线斜，显然黑点破坏了下凸壳性质，那么弹出黑点，显然这样可以使以后求解更优。

在求解取点的时候我们从队尾不断弹出点，直到队尾两个点的斜率大于当前直线，由于斜率递增，显然这些点以后永远不能成为更优解，这时队尾的点就是最优解。

栈的情况：

||斜率递增|斜率递减| |--|--|--| |X递增|max/维护下凸壳|min/维护上凸壳| |X递减|min/维护上凸壳|max/维护下凸壳|

这种时候处理和队列处理相似，对于加入新点，不断弹出栈顶的点使得其符合上凸壳性质，由于斜率递增，那么这些弹出的点永远不会成为更优解；对于求解取点，我们在栈顶不断弹出点使得栈顶两个点的斜率大于当前直线斜率，由于斜率递增，那么这些弹出的点永远不会成为更优解，这时栈顶的点显然是最优解；

小结：由于 X 单调性的所以可以顺序将求出的点放入队列/栈中就可以维护一个按照 X 递增的点集；由于 K 单调性，那么我们可以弹出一些永远不会成为最优解的点，这样对于每个点最多入队/入栈和出队/出栈一次，故时间复杂度是 \mathcal{O}(n)。

X 有单调性 / 线性数据结构维护

由于 X 有单调性我们还是能用线性数据结构存储，因为只会在一头插入不会在中间插入；但由于 K 没有单调性，那么我们就会面临在中间查找一个点的情况，又因为点集中斜率是单调递增的，并且具有连续存储的性质，我们可以二分查找一个点使得斜率最接近这条直线就是最优解。故时间复杂度是 \mathcal{O}(n\log n)。

其余情况

由于 X 没有单调性，那么我们就会面临在中间插入/删除点的情况，又要在中间查找一个点，那么不难想到使用平衡树进行维护点集。

多维斜率优化

dp_{i,j}=\min_{(k,l)\in set_i}\left(Y_{k,l}+K_{i,j}\times X_{k,l}+B_{i,j}\right)

行如这样的多维斜率优化可以考虑划归为一维的情况处理，化为行如这样的形式：

dp_{i+n\times j}=\min_{(k+n\times l)\in set_i}\left(Y_{k+n\times l}+K_{i+n\times j}\times X_{k+n\times l}+B_{i+n\times j}\right)

这个东西可以扩展到n维的斜率优化。

但是这样还是未免有些麻烦，但是对于一些特殊情况我们仍然又一些trick使得求解更简单，例如：

dp_{i,j-1}=\min_{(k,j-1)\in set_i}\left(Y_{k,j-1}+K_{i,j}\times X_{k,j-1}+B_{i,j}\right)

这时我们可以参考滚动数组的方法处理，每一层也就是每一个 i 求解后记录下来，下层求解使用上次记录的数即可，然后滚动记录覆盖。

附录

叉积判断斜率

由于需要斜率判断，对于两个 P,Q 点的斜率。我们使用斜率公式计算 \frac{Y_P-Y_Q}{X_P-X_Q} 但是这样计算需要浮点数，非常有可能爆精度。我们可以换一种方式计算，实际上在正式应用中我们大多数时候是在计算两个斜率的大小关系，假设有 A,B,C,D 四个点，假设有个表达式(当然这个表达式可能为假) K_{A,B}<K_{C,D} 那么则有 \frac{Y_A-Y_B}{X_A-X_B}<\frac{Y_C-Y_D}{X_C-X_D} 如果 X_A-X_B,X_C-X_D 同号的情况下则有 \\left(Y_A-Y_B)*\left(X_C-X_D\right)<\left(Y_C-Y_D\right)\left(X_A-X_B\right) 这样就可以避免精度问题，但是一定注意不等式符号变化问题。

上/下凸壳维护点集正确性证明

在前面的过程中，我们直观感受了在函数图像中能去到最优解的点是一个凸壳，但是缺乏严谨的证明。这里以下凸壳取最小做证明。

定义一个点 P\left(X_P,Y_p\right) 下凸壳在上方表示：对于这个点集按照 X 递增排序，第一个点是 \left(X_1,Y_1\right) 最后一个点是 \left(X_n,Y_n\right) 。对于这 P 点有， X_1\leq X_P \leq X_n ，并且 P 在这个下凸壳中每两个相邻点的直线的上方。

我们发现在维护下凸壳时我们会弹出一些点，而这些点都是在这个下凸壳上方，证明：设 A\left(X_A,Y_A\right) 这个点我们找到在 X 轴上距离最近两个 P\left(X_P,Y_P\right) 和 Q\left(Q_P,Q_P\right) 并且 P 在 Q 左侧，由于 A 在这个下凸壳上方所以 A 在直线 l_{PQ} 上方，并且在线段 PQ 上方，易证 k_{PA} > k_{AQ} 。

那么进而我们可以发现在 A ，在这条直线上方，所以一条求解时某条直线去到 A 点到 X 轴的截距会更大(在 PQ 上方显然截距更大) 。

并且可以发现用线性数据结构维护点集时，用斜率弹出的点都是在下凸壳上方的点。

小结：由于在下凸壳上方的点都会破坏下凸壳性质，剩下的点都是下凸壳点集的点，而下凸壳上方的点不会成为更优解，所以维护下凸壳可以找到最优解。

WQS二分 套上 斜率优化

关于WQS二分详情见"附1：WQS二分简述"。这里如果一个斜率优化限制转移 a 次，可以考虑使用WQS二分，这里只需要将 \operatorname{f}\left(x\right) 计算的式子套上斜率优化即可，并且注意这时的转移方程应该是 dp_i=Y_j-K_iX_j-mid 。算法所以主体是WQS二分，斜率优化。

例题

请读者按照顺序做，层层递进的题目编排。

  1. P3195 [HNOI2008]玩具装箱

  2. P5017 [NOIP2018 普及组] 摆渡车

  3. P2365 任务安排

  4. P3628 [APIO2010] 特别行动队

  5. P2120 [ZJOI2007] 仓库建设

  6. P5785 [SDOI2012]任务安排

  7. P4072 [SDOI2016]征途

  8. P4360 [CEOI2004] 锯木厂选址

  9. P2305 [NOI2014] 购票

  10. P5308 [COCI2018-2019#4] Akvizna

题解在"附2：题目浅析"中。