## 斜率优化
斜率优化的核心思想是将转移方程变为形如 $y = kx +b$ 的形式，这样我们就需要解决 $n$ 个线性规划问题。在第 $i$ 个线性规划问题当中，我们的点集是 $S$，同时有斜率 $k_i$，假设这个线性规划的最小答案（截距）为 $b_i$ 则会向点集中添加一个新点 $(x_i, f(b_i))$，$f$ 是一个因题而异的函数。
考虑以下问题：
1. 所有问题的 $x$ 和 $k$ 单调不降。
由于单调不降，每个问题的决策点一定是往右走的，可以使用**单调队列**来维护下凸壳，查询的时候比较队首的斜率和 $k$ 的大小关系，找到第一个 $\ge k$ 的点，计算截距即可。
加入点的时候由于 $x$ 单调不降，我们可以在队尾比较斜率，弹出一些点上方的点，然后再加入当前点即可。
时间复杂度 $O(n)$
2. 如果 $x$ 单调不降。
依然可以维护单调队列，只不过要二分查找决策点。
3. 没有特殊性质。
可以使用平衡树维护，或者是 CDQ 分治。
需要使用斜率优化的常见特征：
1. 转移方程中既有 $i$ 又有 $j$。
### 例题
#### [P3195 [HNOI2008] 玩具装箱](https://www.luogu.com.cn/problem/P3195)
有显然的 $O(n ^ 2)$ DP。
$$f_i \gets \min\{f_{j - 1} + (i - j + S_i - S_{j - 1} - L)^2\}$$
其中 $f(i)$ 代表最后 一个元素被包含在容器里，最小代价，而 $S_i$ 代表 $\sum_{j=1}^i C_j$ ，说白了就是前缀和。
#### ~~错误示范~~复杂方法
考虑将 $f(i)$ 化为 $l:y = kx+b$ 的形式，为了方便表示，记 $p_i = S_i + i$，$L' = L + 1$且省略了 $\min$，原式可化简为：
$$f_i = f_{j - 1} + (p_i-p_{j-1}-L')^2$$
将 $p_i - p_j$ 看成一个整体， 将平方拆开可得：
$$f_i = f_{j - 1} + (p_i - p_{j-1})^2-2L'(p_i-p_{j-1})+L'^2$$
再次开方可以得到：
$$f_i=f_{j - 1} + p_i^2 + p_{j-1}^2 - 2p_ip_{j-1} - 2L'p_i+2L'p_{j-1}+L'^2$$
运用常见的思想，将拥有相同字母的放在同一边：
$$f_i-p_i^2+2L'p_i-L'^2=f_{j-1}+p_{j-1}^2-2p_ip_{j-1}+2L'p_{j-1}$$
稍微整理可得：
$$ f_i-p_i^2+2L'p_i-L'^2=f_{j-1}+2L'p_{j-1}+p_{j-1}^2-2p_ip_{j-1}$$
$${\color{Red} f_i-p_i^2+2L'p_i-L'^2} ={\color{Orange} f_{j-1}+2L'p_{j-1}+p_{j-1}^2} {\color{Blue} -2p_i} {\color{Green} p_{j-1}} $$
其中 $y_i=f_i-p_i^2+2L'p_i-L'^2$，$b_i=f_{j-1}+2L'p_{j-1}+p_{j-1}^2$，$k_i = p_{j - 1}$，$x_i=2p_i$。
可以写成 $y=b-xk$。
~~很显然 $k$ 和 $x$ 是单调不降的，可以使用方法 $1$，维护下凸壳即可。~~
~~然后你发现你推错式子了，其实我们的 $k_i$ 前面还有一个负号，$k_i$ 是单调递减的，而 $x_i$ 是单调递增的。~~
其实你并没有推错式子，考虑两边同乘负号。
$$p_i^2+L'^2-2L'p_i-f_i = 2p_ip_{j-1}-f_{j-1}-2L'p_{j-1}-p_{j-1}^2$$
此时 $y_i=p_i^2+L'^2-2L'p_i-f_i$，$b_i=-f_{j-1}-2L'p_{j-1}-p_{j-1}^2$，$k_i = p_{j - 1}$，$x_i=2p_i$。
现在的 $x$ 和 $k$ 是真的不降了。
#### ~~正确解法~~更简单的做法
先把原式搬过来：$f_i \gets \min\{f_{j - 1} + (i - j + S_i - S_{j - 1} - L)^2\}$
先整理式子可得：
$$f_i = f_{j} + (i + S_i - 1 - L - (S_j + j))^2$$
令 $a_i = i + S_i - 1 - L$，$b_j = S_j + j$，原式可化简为：
$$f_i = f_j + (a_i-b_j)^2$$
拆平方可得：
$f_i = f_j + a_i^2+b_j^2-2a_ib_j$
略微化简可得 $-f_i +a_i^2= f_j - b_j^2 + 2a_ib_j$
令 $x = 2b_j$，$k = a_i$ 很显然二者都是单调不降，可以使用方法 $1$。