斜率优化 DP 笔记
Conan15
·
·
算法·理论
Upd on 2025.11.05：例 3 公式错误。
零、闲话
更坏的阅读体验
本文提供一套斜率优化 DP 较为通用的解题方法，由于大部分题目技巧共通，所以限于篇幅不会作太深入的分析，只会对几道经典题详细解释。
今天是 2025.10.31，祝大家 CSP-S2025 RP++。\
这是四个月前写的东西了，现在才想起来没搬到洛谷。
本文 markdown 的颜色渲染好像有点问题，把大括号也一起染色了，不过不影响阅读。
之前自学的时候总是找不到一个合适的理解方法。\
还会遇到各种奇怪的问题：例如“什么类型的式子可以斜率优化？”“什么情况要用什么类型的优化？”……等等。
另外网上的笔记要么不详细，要么冗余的部分很多，例如：
- 这篇 虽然详细，但排版凌乱废话较多。
- 根本就没有必要证明决策单调性。
不过写得还是蛮好的。
是时候解决这些问题了。
一、引入
这个引入可能比较奇怪……但它确实很好地描述了斜率优化的本质。
你需要维护一个点集 (x_i,y_i)，每次给定 k，q 次查询 k x_i + y_i 的最大值。
上述问题等价于给定 (a,b)，求 a x_i + b y_i 的最大值，当只给 k 相当于是查询 \frac{a}{b} x_i + y_i 的最大值（如果 b \lt 0 就怎么取反一下求最小值即可）。
- 考虑 a=1,b=0，相当于查询 X 方向上距离原点最远的点。
- 考虑 a=0,b=1，相当于查询 Y 方向上距离原点最远的点。
- 扩展到一般的 (a,b)，相当于查询 (0,0)-(a,b) 这条线上距离原点最远的点。
然而，这个点一定在凸包上，否则考虑反证，一定存在更远的点。
凸包相关-计算几何初步
于是现在只考虑简化版的问题：给定 k 求 k x_i + y_i 的最大（小）值。\
这样转化模型就可以解释斜率优化中一个很重要的点：\max 决策维护上凸壳，\min 决策维护下凸壳。 原因显然。
以 \max 为例，如何在上凸壳找到最优解？\
并不难发现，“远近”一定是单峰的。\
考虑把“远近”刻画成在 (0,0)-(k,1) 直线上的投影，由于凸包的凸性，距离显然是单峰，有单调性。\
单调性！二分！ 不对，三分！
其实二分和三分都可以做。\
三分显然可以解决，因为函数单峰。\
至于二分，每次选中一个点 mid，判定它和它后一个点之间的斜率是上升还是下降的即可，对于 \max 决策，只需要求最左边的点使得它和它下一个点斜率下降，这是好求的。\
至此，这个问题可以在 O(q \log n) 的复杂度内解决。
还有更优的复杂度！\
考虑把 k 离线下来排序，这样保证按顺序处理的时候 k 单调。\
----------
上面大概做的事情就是**维护一个点集（凸壳），支持根据参数查找函数最值**。\
函数**最值**这件事情启发我们将其运用在**动态规划决策单调性**方面的优化。
# 二、斜率优化
~~老师说不要学这种推法，没有几何直观。~~\
但至少可以总结出来一种比较模板化的解题方法。\
而且试了很多次，还挺顺的。
## 大致流程
（假设 $i$ 从 $j$ 转移而来）
1. 分离和 $j$ 无关的参数 $c$。
2. 提取只和 $j$ 有关的参数 $y$。
3. 确定 $k, x, y, c$。
4. 推式子。
5. 确定维护方法。
## 注意事项
1. 推式子的时候，如果移项有**负数**，要变号。
2. $\color{red}{需要根据实际的式子确定怎样维护上（下）凸壳}$。
- 若 $k$ 单调递减 $x$ 单调递增，直接用**单调队列**维护，取队头转移 $O(n)$。
- 若 $k$ 单调递增 $x$ 单调递增，需要用**单调栈**维护，取栈顶转移 $O(n)$。
- 若只有 $x$ 单调递增，依然采用**单调队列**，但需要**二分查找**最优决策 $O(n \log n)$。
- 找到一个点使得左边斜率和右边斜率分别大于或小于某个值。
- 若 $k, x$ 均不单调，可以用 **CDQ 分治思想或李超线段树**维护，好像也可以用**平衡树**吧 $O(n \log n)$。
3. 观察初始式子是否能化为“只和 $i$ 有关项”“只和 $j$ 有关项”“和 $i, j$ 都有关项”，再尝试斜率优化。在推式子之前应当先尝试是否有更简单或更显然的优化方法。
----------
# 三、例题
题目**大致**按个人认为的难度排序。
## 例 1：[AT_dp_z Frog 3](https://www.luogu.com.cn/problem/AT_dp_z)
这是我写的第一道斜率优化，其它一般都是该题的变种或加上各种参数。\
以这道经典题把斜率优化的流程大致过一遍。\
个人认为这篇题解写得很好：[学习链接](https://www.luogu.com.cn/article/ta88qdqn)。\
显然有：
$$dp_i = \min\limits_{j=0}^{i-1} \{ dp_j + (h_i - h_j)^2 + C \}$$
### 第一步：分离和 $j$ 无关的参数。
$$dp_i = \min\limits_{j=0}^{i-1} \{ dp_j - 2h_ih_j + h_j^2 \} + C + h_i^2$$
### 第二步：提取只和 $j$ 有关的参数。
设 $y(j) = dp_j + h_j^2$：
$$dp_i = \min\limits_{j=0}^{i-1} \{ y(j) - 2h_ih_j \} + C + h_i^2$$
### 第三步：确定 $k, x, y, c$。
$$dp_i = \min\limits_{j=0}^{i-1} \{ \color{blue}{-2h_i} \color{red}{h_j} + \color{green}{y(j)} \} + \color{purple}{C + h_i^2}$$
对于上式，有 $\color{blue}{k=-2h_i}, \color{red}{x=h_j}, \color{green}{y = y(j)}, \color{purple}{c = (C + h_i^2)}$。\
相当于是求 $kx+y$ 的**最小值**，维护**下凸壳**，最后加上常数 $c$。
### 第四步：推式子
一般是把 $k,x,y$ 带进去形成不等式，移项推出只和 $k$ 相关的不等式：
设 $j_1 \lt j_2$，且 $j_1$ 的决策比 $j_2$ 更优，则有：
$$k x_1 + y_1 \leq k x_2 + y_2$$
$$k(x_1 - x_2) \leq y_2 - y_1$$
将 $x,y$ 带进去：
$$k( h_{j_1} - h_{j_2} ) \leq y(j_2) - y(j_1)$$
移项，注意本题 $h$ 单调递增所以要变号，同时把 $k=-2h_i$ 代入：
$$-2h_i \geq \frac{y(j_2) - y(j_1)}{x_1 - x_2}$$
$$2h_i \leq \frac{y(j_1) - y(j_2)}{x_1 - x_2}$$
### 第五步：确定维护方法
右边长得像一个**斜率**的式子，这意味着我们用 $k=2h_i$ 的直线去“逼近”这个下凸壳，通过之前说的二分方法就可以找到最优决策进行转移。\
由于要维护下凸壳，并且我们在 DP 要支持**动态加入点**，所以考虑用**单调队列**维护这个过程。\
具体地，对于队列中的元素，必须保证**两两之间斜率单调上升**。
之前说过可以用二分找到队列中的最优决策点，但此时不需要这么麻烦。\
由于我们用 $k=2h_i$ 去逼近，而 $h_i$ 又是**单调递增**的，所以**最优决策点单调向后移动**，在单调队列中不断**弹出队头**去掉不优的决策即可。
```cpp
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 15;
int n, h[N];
long long C;
int q[N], st, ed;
long long dp[N];
double x(int p) { return h[p]; }
double y(int p) { return dp[p] + h[p] * 1ll * h[p]; }
double slope(int a, int b) {
return (y(b) - y(a)) * 1.00 / (x(b) - x(a));
}
int main() {
scanf("%d%lld", &n, &C);
for (int i = 1; i <= n; i++) scanf("%d", &h[i]);
st = ed = 1, q[ed] = 1;
for (int i = 2; i <= n; i++) {
while (st < ed && slope(q[st], q[st + 1]) <= 2 * h[i]) st++;
int j = q[st];
dp[i] = dp[j] + (h[i] - h[j]) * 1ll * (h[i] - h[j]) + C;
while (st < ed && slope(q[ed - 1], q[ed]) >= slope(q[ed], i)) ed--;
q[++ed] = i;
}
printf("%lld\n", dp[n]);
return 0;
}
```
## 例 2：[洛谷 P3195 [HNOI2008] 玩具装箱](https://www.luogu.com.cn/problem/P3195)
并不难写出普通转移方程（设 $s$ 为 $c$ 的前缀和）：
$$dp_i = \min\limits_{j=0}^{i-1} \{ dp_j + (i-j-1+s_i-s_j-L)^2 \}$$
考虑暴力展开平方，发现有整整 $36$ 项，爽飞了。\
推式子需要一些手法……考虑我们斜率优化之前要做什么？\
**分离 $i, j$ 相关的项。**\
所以设 $a_i = s_i + i, b_j = s_j + j + L + 1$，所以式子就简化为：
$$dp_i = \min\limits_{j=0}^{i-1} \{ dp_j + (a_i - b_j)^2 \}$$
$$dp_i = \min\limits_{j=0}^{i-1} \{ -2a_ib_j + dp_j + b_j^2 \} + a_i^2$$
一样地，设 $j_1 \lt j_2$，且 $j_1$ 比 $j_2$ 优……然后和上一题类似，最后的式子是：
$$2 a_i \leq \frac{y_1 - y_2}{x_1 - x_2}$$
$a, b$ 都单增，所以 $k, x$ 都单增，因此直接单调队列维护即可。
## 例 3：[洛谷 P5785 [SDOI2012] 任务安排](https://www.luogu.com.cn/problem/P5785)
一道很经典的斜率优化题，也是蓝书上的斜优入门题，就详细记录一下吧。
朴素 DP：
由于我们需要知道 $S$ 被计算了几次，所以相应的也需要知道这是第几批次的任务。\
设 $dp_{i,j}$ 表示分了 $i$ 批次完成前 $j$ 个任务的最小代价。\
记 $st,sc$ 分别为 $t,c$ 的前缀和。\
则有转移式：
$$dp_{i,j}=\min\limits_{0 \leq k \lt j} \{ dp_{i-1,k} + (S \times i + st_j) \times (sc_j - sc_k) \}$$
注意是 $sc_j - sc_k$ 不是 $sc_j - sc_{k-1}$。\
这样空间是 $O(n^2)$，时间复杂度是 $O(n^3)$。由于卡空间需要滚动数组优化到 $O(n)$。
----------
蓝书上介绍了一种**费用提前计算**的思想。\
设 $dp_{i}$ 表示把前 $i$ 个任务分成若干组的最小代价。\
发现对于每一组任务，$S$ 的贡献计算是单增的。即 $S,2S,3S,\dots,kS$。\
根据分配律，考虑把代价的计算中 $st$ 和 $S$ 的部分分开来计算。在当前任务提前计算好后面任务中 $S$ 的贡献。
即：
$$dp_{i} = \min\limits_{0 \leq j \lt i} \{ dp_{j} + (sc_i - sc_j) \times st_i + (sc_n - sc_j) \times S \}$$
此时空间复杂度是 $O(n)$，时间复杂度 $O(n^2)$，可以通过弱化版。
----------
现在 $n \leq 3 \times 10^5$，考虑 $O(n)$ 等更优的做法。
$$dp_{i} = \min\limits_{0 \leq j \lt i} \{ dp_{j} + (sc_i - sc_j) \times st_i + (sc_n - sc_j) \times S \}$$
设求 $dp_i$ 时，$j_1 \lt j_2 \lt i$，并且 $j_1$ 优于 $j_2$。
则有：
$$dp_{j_1} + (sc_i - sc_{j_1}) \times st_i + (sc_n - sc_{j_1}) \times S \leq dp_{j_2} + (sc_i - sc_{j_2}) \times st_i + (sc_n - sc_{j_2}) \times S$$
$$dp_{j_1} + sc_i \times st_i - sc_{j_1} \times st_i + sc_n \times S - sc_{j_1} \times S \leq dp_{j_2} + sc_i \times st_i - sc_{j_2} \times st_i + sc_n \times S - sc_{j_2} \times S$$
$$dp_{j_1} - sc_{j_1} \times st_i - sc_{j_1} \times S \leq dp_{j_2} - sc_{j_2} \times st_i - sc_{j_2} \times S$$
$$dp_{j_1} - dp_{j_2} - sc_{j_1} \times S + sc_{j_2} \times S \leq sc_{j_1} \times st_i - sc_{j_2} \times st_i$$
移项注意负数变号。
$$\frac{dp_{j_1} - dp_{j_2} - (sc_{j_1} - sc_{j_2}) \times S}{sc_{j_1} - sc_{j_2}} \geq st_i$$
$$\frac{dp_{j_1} - dp_{j_2}}{sc_{j_1} - sc_{j_2}} - S \geq st_i$$
取 $\min$，所以单调队列维护**下凸壳**。\
由于 $st_i$ 单增，可以直接取队头进行转移。
一定不要把 `slope(q[l-1],q[l])` 写成 `slope(l-1,l)`。\
~~这是很久以前写的题解了。~~\
这么推会有点麻烦，事实上可以先找出 $x, y$ 然后**换元**，推完再代入进去会更顺。
## 例 4：[洛谷 P3628 [APIO2010] 特别行动队](https://www.luogu.com.cn/problem/P3628)
设 $S$ 表示 $x$ 的前缀和。
$$dp_i = \max\limits_{j=0}^{i-1} \{ dp_j + A(s_i-s_j)^2 + B(s_i-s_j) + C \}$$
看到平方就应该很敏锐地发现是斜优了，因为平方是很明显的 $i,j$ 各部分相关的形式。\
和之前相同地，一样转化形式：
$$dp_i = \max\limits_{j=0}^{i-1} \{ \color{blue}{-2As_i}\color{red}{s_j} + \color{green}{dp_j + As_j^2 - Bs_j} \} + \color{purple}{As_i^2 + Bs_i + C}$$
推式子：
$$2As_i \geq \frac{y_1 - y_2}{x_1 - x_2}$$
取 $\max$ 决策，上凸壳；$A \lt 0$ 所以 $k$ 单减 $x$ 单增，单调队列队头转移。
于是把 $x, y$ 带进去就做完了。
## 例 5：[洛谷 P2900 [USACO08MAR] Land Acquisition G](https://www.luogu.com.cn/problem/P2900)
首先发现如果一个矩形被另一个矩形完全包含，则它一定不会对答案有贡献。\
因此使用**单调栈** $O(n)$ 处理出有用的矩形，画在平面直角坐标系上 应该是个阶梯状的东西。
之后 $O(n^2)$ DP 是简单的，设 $f_i$ 表示前 $i$ 片土地分组的最小代价。
$$f_i = \min\limits_{j=1}^{i-1} dp_{j-1} + x_i \times y_j$$
所以考虑优化，发现这东西 $i,j$ 相关的项分别相乘，就很斜率。\
由于式子很简单，而且换元又会有变量名冲突，可以直接对原式推导：
设 $j_1 \lt j_2$ 且 $j_1$ 优于 $j_2$：
$$x_i \times y_{j_1} + dp_{j_1} \leq x_i \times y_{j_2} + dp_{j_2}$$
移项，注意 $y_j$ 单调递减要变号。
$$x_i \geq \frac{dp_{j_1} - dp_{j_2}}{y_{j_1} - y_{j_2}}$$
$k, x$ 都递增，可以直接队头转移。
## 例 6：[洛谷 P2120 [ZJOI2007] 仓库建设](https://www.luogu.com.cn/problem/P2120)
设 $f_i$ 表示强制建 $i$ 以保护 $[1,i]$ 物品的最小代价。\
则容易写出状态转移方程，枚举上一次在 $j$ 建立仓库：
$$f_i = \min\limits_{j=0}^{i-1} \{ f_j + c_i + (\sum\limits_{k=j+1}^{i-1} (x_i - x_k) \times p_k) \}$$
把式子拆一下，得到：
$$f_i = \min\limits_{j=0}^{i-1} \{ f_j + ( \sum\limits_{k=j+1}^{i-1} p_k ) \times x_i - (\sum\limits_{k=j+1}^{i-1} x_k \times p_k) \} + c_i$$
设 $sp$ 为 $p$ 前缀和，$s$ 为 $x \times p$ 前缀和。
$$f_i = \min\limits_{j=0}^{i-1} \{ f_j + (sp_{i-1} - sp_j) - (s_{i-1} - s_j) x_i \} + c_i$$
$$f_i = \min\limits_{j=0}^{i-1} \{ \color{green}{f_j - sp_j} + \color{blue}{s_j} \color{red}{x_i} \} + \color{purple}{ c_i + sp_{i-1} - s_{i-1} }$$
然后设 $j_1 \lt j_2$，但 $j_1$ 优于 $j_2$，移项得到：
$$x_i \leq \frac{(f_{j_1} + s_{j_1})-(f_{j_2} + s_{j_2})}{sp_{j_1} - sp_{j_2}}$$
$x, k$ 都单调递增，直接单调队列队头转移。
## 例 7：[洛谷 P5504 [JSOI2011] 柠檬](https://www.luogu.com.cn/problem/P5504)
假设 $c_i$ 表示 $a_i$ 颜色中 $i$ 是第 $c_i$ 个出现的。\
则不难写出转移方程：
$$dp_i = \max\limits_{j \leq i, a_i = a_j} \{ dp_{j-1} + a_i \times (c_i - c_j + 1)^2 \}$$
看到平方，果断拆式子：
$$dp_i = \max\limits_{j \leq i, a_i = a_j} \{ dp_{j-1} + a_i \times (c_i^2 + c_j^2 + 1 - 2c_ic_j + 2c_i - 2c_j) \}$$
提取 $k, x, y, c$：
$$dp_i = \max\limits_{j \leq i, a_i = a_j} \{ \color{green}{dp_{j-1} + c_j^2a_j - 2c_ja_j} \color{blue}{-2c_ia_i}\color{red}{c_j} \} + \color{purple}{a_i + a_ic_i^2 + 2a_ic_i}$$
然后再假设 $j_1 \lt j_2$，$j_1$ 优于 $j_2$，得到：
$$2a_ic_i \geq \frac{y_1 - y_2}{x_1 - x_2}$$
由于 $k, x$ 双单增，需要用单调栈维护（卡了很久单调队列）。
## 例 8：[洛谷 P5017 [NOIP 2018 普及组] 摆渡车](https://www.luogu.com.cn/problem/P5017)
设 $f_i$ 表示运走前 $i$ 个单位时间来的人，最小的等待时间是多少。\
容易得到转移方程：
$$f_i = \min\limits_{j=0}^{i-m} \{ f_j + \sum\limits_{j \lt t_k \leq i} (i - t_k) \}$$
第一想法是通过 $i,j$ 二分出 $t$ 序列合法的 $l,r$，但显然由于 $t$ 足够小可以直接在上面做**前缀和**。\
前缀和优化一下，记 $s$ 为 $t$ 的前缀和，$c$ 为 $[0,i]$ 时间内来了多少人。
$$f_i = \min\limits_{j=0}^{i-m} \{ f_j + (c_i - c_j) \times i - (s_i - s_j) \}$$
复杂度 $O(T^2)$。
然后可以减少无用转移：发现 $\geq 2m$ 的段**分成两部分 $m$ 一定不劣**，所以减小转移范围，复杂度 $O(Tm)$。
还有优化空间！再看一眼式子：
$$f_i = \min\limits_{j=\max(0, i-2m+1)}^{i-m} \{ f_j + (c_i - c_j) \times i - (s_i - s_j) \}$$
乘积形式已经出来了，那么展开后，照常推式子。\
结果是：
$$\frac{(f_{j_1} + s_{j_1}) - (f_{j_2} + s_{j_2})}{c_{j_1} - c_{j_2}} \geq i$$
这玩意儿的 $k=i$ 是单增的，$x=c_j$ 也是单增的，所以可以直接**单调队列队头**转移。
## 例 9：[洛谷 P4072 [SDOI2016] 征途](https://www.luogu.com.cn/problem/P4072)
平均数：
$$\bar{s} = \frac{\sum\limits_{i=1}^{m} s_i}{m}$$
方差：
$$v = \frac{1}{m} \sum\limits_{i=1}^{m} (s_i - \bar{s})^2$$
$$v = \frac{1}{m} \Big[ \sum\limits_{i=1}^{m} s_i^2 - 2 \bar{s} (\sum\limits_{i=1}^{m} s_i) + m \bar{s} ^2 \Big]$$
化简得：
$$v \times m^2 = m \times (\sum s_i^2) - (\sum s_i)^2$$
后者是定值，前者系数 $m$ 也是定值，因此**只要最小化 $\sum s_i^2$ 即可**。\
$O(m n^2)$ DP 是显然的，设 $dp_{i,j}$ 表示走了 $i$ 天，走到 $j$ 这条路，最小代价是多少。
下文 $s$ 为**路径的前缀和**。\
则有 $dp_{i,j} = \min\limits_{0 \leq k \lt j} \{ dp_{i-1,k} + (s_j - s_k)^2 \}$。
----------
然后注意到**平方**，这是一个很典的**斜率优化**的式子。\
拆式子：
$$\min\limits_{0 \leq k \lt j} \{ dp_{i-1,k} + (s_j - s_k)^2 \}$$
$$\min\limits_{0 \leq k \lt j} \{ \color{green}{dp_{i-1,k} + s_k^2} \color{blue}{-2s_k} \times \color{red}{s_j} \} + \color{purple}{s_j^2}$$
还是设 $k_1 \lt k_2$，$k_1$ 优于 $k_2$：
$$dp_{i-1,k_1} + s_{k_1}^2 - 2s_{k_1} \times s_j \leq dp_{i-1,k_2} + s_{k_2}^2 - 2s_{k_2} \times s_j$$
$$s_j \geq \frac{y(k_1) - y(k_2)}{x(k_1) - x(k_2)}$$
$$s_j \geq \frac{(dp_{i-1, k_1}+s_{k_1}^2)-(dp_{i-1,k_2}+s_{k_2}^2)}{s_{k_1}-s_{k_2}}$$
挺巧的，$k,x$ 都是 $s_j$，且是单增的，所以直接**单调队列**维护，取队头转移就完事了。
## 例 10：[CF311B. Cats Transport](https://www.acwing.com/solution/content/256906/)
首先考虑 $a_i \leftarrow t_i - \sum\limits_{j=2}^i d_{h_i}$，即算出一个铲屎官最早什么时候出发能带走这只猫。\
然后就和 $h_i$ 无关了，再把 $a$ 排序，每次相当于选取一段区间，代价是区间每个数与区间最大值差的绝对值之和。\
容易想到二维 DP 状态 $dp_{i,j}$ 表示前 $j$ 个分成 $i$ 组的最小代价。
设 $s_i$ 为 $a$ 的前缀和，优化一下：
$$dp_{i,j} = \min\limits_{0 \leq k \lt j} \{ dp_{i-1,k} + a_j \times (j-k) - (s_j - s_k) \}$$
这样时间复杂度是 $O(p m^2)$ 的。\
然后看到相乘直接斜率优化。
$$dp_{i,j} = \min\limits_{0 \leq k \lt j} \{ \color{green}{dp_{i-1,k} + s_k} \color{blue}{-a_j} \color{red}{k} \} + \color{purple}{a_j \times j - s_j}$$
仍然设 $k_1 \lt k_2$，$k_1$ 决策优于 $k_2$，推导得到：
$$\frac{(dp_{i-1,k_1} + s_{k_1}) - (dp_{i-1,k_2} + s_{k_2})}{k_1 - k_2} \geq a_j$$
双单增，直接单调队列维护下凸壳，队首转移。
## 例 11：[洛谷 P5468 [NOI2019] 回家路线](https://www.luogu.com.cn/problem/P5468)
很好玩的题，自己推出来了。（虽然最后还是翻题解才发现自己哪里错了……）
这个贡献式子是二次的，而且还和 $u, v, p, q$ 至少四个参数相关，很吓人。\
第一反应是考虑 DP 做这个事情，由于涉及点之间的转移，以及时间先后的问题，所以，设 $dp_{u, i}$ 表示在 $i$ 时刻到达 $u$ 点的最小烦躁值。\
假设有一条边 $u \to v$，出发时间 $p$ 到达时间 $q$，则不难写出如下方程：
$$dp_{v, q} \leftarrow dp_{u, i} + A(p-i)^2 + B(p-i) + C \quad \quad (i \leq p)$$
其实就是枚举 $i$ 时刻到达 $u$ 点，然后通过该线路转移到 $v$。\
这个式子有两个问题：
1. 空间和时间都爆了。
2. 在求 $dp_{v,q}$ 的时候需要保证 $dp_{u,i}$ 都已经计算完。
这里我纠结了挺久的，以为只要保证 $\forall i, dp_{u}$ 被计算完成就行了，接着可以怎么动态开点优化一下空间，时间复杂度再说。\
但事实是，这张图**不一定是 DAG，不能拓扑排序**。
----------
那么不妨跳出来重新看问题，我们只需要保证 $\forall i \leq q, dp_{u,i}$ 被计算完。\
所以显而易见地，可以按照 $q$（到站时刻）将所有线路**排序**，依次插入这些线路。\
然后新的问题是，DP 是否有后效性？显然不会，就算有环再绕回来，它也只能影响后面的时刻这个点的 DP 信息。
接下来考虑先排序，然后在上述算法的基础上优化时空复杂度。\
首先不需要真的开两维的 dp 数组，因为对于一个点 $v$ 有用的状态只有 $\forall (u \to v, p, q)$ 中的 $dp_{v, q}$。
因此动态开点（vector）存 DP 值即可。\
然后是时间复杂度的问题。
----------
看到平方贡献，想到拆式子 **斜率优化**。
$$\min \{ dp_{u, i} + A(p^2-2ip+i^2) + B(p-i) + C\}$$
$$\min \{ \color{green}{dp_{u, i}+Ai^2-Bi} \color{blue}{-2Ap} \color{red}{i} \} \color{purple}{+ Ap^2 + Bp + C}$$
于是得到 $k, x, y, c$，接下来推式子，设 $i_1 \lt i_2$，则有：
$$kx_1 + y_1 \leq kx_2 + y_2$$
$$2Ap \leq \frac{y_1 - y_2}{x_1 - x_2}$$
观察形式：取 $\min$ 维护下凸壳，$x$ 单调递增但 $k$ 不单调，所以用**单调队列二分**维护。\
然后愉快地 WA 了洛谷 `#9 #19` 两个点。
> 之前的做法是按 $q$ 排序，每次把当前的 $u \to v$ 完成转移之后**直接扔进 $v$ 的单调队列里面**。\
> 问题是，$p$ 的查询**不具有单调性**，所以如果之后有从 $v$ 出发的列车，最优决策**可能会被刚刚扔进去的覆盖掉**。\
> 所以正确做法是：**按照 $p$ 排序**，每次把 $\leq p$ 的所有待加入 DP 值扔进对应点的单调队列，更新完当前节点 $v$ 的 DP 值之后也把它先存着，延后再加入。
由于红温了所以代码整得很丑……~~最初一版的代码其实还挺好看的。~~
## 例 12：[洛谷 P3994 高速公路](https://www.luogu.com.cn/problem/P3994)
不难想到设 $f_i$ 表示从 $i$ 跳到根节点的最小代价。
$$f_i = \min\limits_{j \in pa_i} \{ dp_j + (dep_i - dep_j) p_i + q_i \}$$
有 $i,j$ 相关项相乘的形式！**斜率优化**！
$$f_i = \min\limits_{j \in pa_i} \{ \color{green}{dp_j} \color{blue}{-p_i} \color{red}{dep_j} \} + \color{purple}{dep_i p_i + q_i}$$
设 $dep_{j_1} \lt dep_{j_2}$，且 $j_1$ 比 $j_2$ 更优。
$$k(x_1 - x_2) \leq y_2 - y_1$$
移项，$x$（$dep$）单增，负数变号：
$$k \leq \frac{y_2 - y_1}{x_1 - x_2}$$
$$p_i \geq \frac{y_1 - y_2}{x_1 - x_2}$$
$k, x$ 都单增，可以**单调队列队头转移**。
但这是一棵树，怎么做斜率优化呢？\
如果在从根开始 dfs 的过程中直接维护单调队列，难免会有元素覆盖的情况。\
本质上问题就是：**一棵子树会影响另一棵子树的下凸壳**。
如果暴力弹出加入（还原现场）是 $O(n^2)$ 的复杂度，那么就不弹出加入了。\
**队头不弹出**，直接保留**完整下凸壳**，转移的时候**二分决策点**是 $O(n \log n)$ 的。\
然后处理加入元素的问题：发现实际上由于下凸壳的斜率具有**单调性**，可以**二分出队尾弹出到哪里**，然后加入一个新元素 $u$ 只会覆盖原来的一个元素，只需要维护这个东西最后再复原即可。
核心思想就是**利用二分快速查找**，以及**利用队列弹出队尾之后每次只加入一个元素**，把覆盖掉的那个元素给记录一下即可。\
更详细地，就是**队尾指针移动了，但元素还在**。
## 例 13：[洛谷 P4027 [NOI2007] 货币兑换](https://www.luogu.com.cn/problem/P4027)
发现一个重要性质：**每次买进一定买完，卖出一定卖完。**\
如果买进的券在未来可以让你赚钱，那你一定是买完最优，而卖出同理。
那么显然可以干出来一个 $O(n^2)$ 的 DP，设 $f_i$ 为前 $i$ 天能获得的最大收益，考虑枚举 $j$ 表示在 $j$ 这一天**买入所有券**，第 $i$ 天再买回来。\
不妨设 $s_i = \max\limits_{j=1}^{i} f_j$。\
若第 $j$ 天买了 $x$ 张 $A$ 券和 $y$ 张 $B$ 券，设 $y_j = t, x_j = R_j t$。
$$R_j t \times A_j + t \times B_j = s_j$$
解得：
$$t = \frac{s_j}{R \times A_j + B_j}$$
$$x_j = \frac{R \times s_j}{R \times A_j + B_j} \quad y_j = \frac{s_j}{R \times A_j + B_j}$$
转移式：
$$f_i = \max\limits_{j=1}^{i-1} \{ x_j \times A_i + y_j \times B_i \}$$
这和 **斜率优化** 本帖一开始引入的问题是几乎相同的。\
借用类似的思路，我们将 $ax + by$ 转化为 $kx+b$ 的形式（同除 $B_i$）：
$$f_i = \max\limits_{j=1}^{i-1} \{ B_i ( \frac{A_i}{B_i} x_j + y_j) \}$$
**它两维都不单增**，可以 CDQ 分治或者平衡树维护上凸壳。\
也可以**李超线段树**维护。
具体地，“反客为主”。\
对于**一次函数** $y=kx+b$，原本 $\frac{A_i}{B_i}$ 是 $k$，$x_j, y_j$ 分别是 $x,b$。\
现在反过来，令 $x = \frac{A_i}{B_i}$，对于每一个 $j$ 相当于一条直线 $k=x_j, b=y_j$。\
相当于维护 $j \in [1, i-1]$ 这些直线在 $x = \frac{A_i}{B_i}$ 处的最大取值，这是李超线段树的模板题。