模板及讲解
斜率优化解决什么问题
DP方程形如$dp(i)=\min(dp(j)+(a_i-a_j)^2)$，有像$(a_i-a_j)^2$这样与$i, j$都相关的信息，就不能用单调队列等来优化，要利用斜率优化来做。
斜率优化
例题：Bzoj 1010
有$n$个数${C_n}$，分成连续的若干段，每段（假设从第$j$个到第$i$个组成一段）的分数为$(X-L)^2$，$X$为$j-i+ \sum C_k , i \leq k \leq j$，其中$L$是一个常量。目标：各段分数的总和最小。
设$dp(i)$表示分组完前$i$件物品的最小花费, $sum_i$表示是前$i$件物品的长度和。
$dp(i)=\min(dp(j)+(sum_i-sum_j+i-j-L-1)^2|1 \leq j < i)$
设$S_i=sum_i+i$，则$dp(i)=\min(dp(j)+(S_i-S_j-L-1)^2)$
设$P=L+1$, 代入，$dp(i)=dp(j)+(S_i-S_j-P)^2$
证明决策单调性
使用数学归纳法证明。
假设$i$前有两个决策$j, k(j < k)$, 且决策$k$比$j$优，则
$$dp(j)+(S_i-S_j-P)^2 > dp(k)+(S_i-S_k-P)^2 –(1)$$
假设$i$后面的某状态$t$有$S(t)=S(i)+v$，则
$$dp(j)+(S_t-S_j-P)^2 > dp(k)+(S_t-S_k-P)^2$$
$$dp(j)+(S_i-S_j-P)^2 +2v(S_i-S_j-P) + v^2 > dp(k)+(S_i-S_k-P)^2 +2v(S_i-S_k-P) + v^2$$
因为$S_i-S_j > S_i-S_k$并且$P \in \mathbb N+$，所以$S_i-S_j-P > S_i-S_k-P$，综合(1)，假设(1)成立
用点来求斜率即可。
斜率斜截式
将常数、仅和$i$相关的项、仅与$j$相关的项、$i、j$乘积项分开
分解，$dp(i)=dp(j)+S_i^2-2S_i \cdot (S_j + P) + (S_j+P)^2$
移项，$2S_i \cdot (S_j+P)+dp(i)=dp(j)+S_i^2+(S_j+P)^2$
$dp(j)+(S_j+P)^2+S_i^2=dp(i)+2S_i(S_j+P)$
把左边($dp(j)+(S_j+P)^2+S_i^2$)看成平面直角坐标系的$y$坐标，右边的$2(S_j+P)$看成$x$坐标。
那么这就是一条$k=S_i, b=dp(i)$的直线方程。决策$j$可以表示为坐标$(2(S_j+P), dp(j)+S_i^2+(S_j+P)^2)$
这里每一条直线的$x$都单调递增，$k$也单调递增。且对于同一个$i$，$k$为定值，所以我们对于每个$i$转移时只需要在知道斜率的情况下将截距$b=dp(i)$最小化。
决策的舍弃 (l)
那么现在问题转化为斜率为$S_i$的直线过一个决策$j$($j$点)，求出截距最小的那一条直线。
那么如果过了$j$点就代表从$j$状态转移到$i$。现在有以下情况：
$k_{AB}$的斜率比直线斜率$S_i$小，那么就要舍弃$A$点。后面点更优，因为
直线过$A$点时
直线过$B$点时
比较
显然在$B$点截距$dp(i)$更小，比$A$点更优，并且直线斜率单增，以后所有的斜率都不会从$j$转移。
因为符合决策单调性，$k$递增，所以用单调队列维护点，实际上是维护了一个凸壳。如果在单调队列中，$k_{q_{l}q_{l+1}} < S_i$，那么就要舍弃$l$.
对于一条斜率为$k$的直线，将他放到凸壳中的应该排的位置即为最优决策点。由于$S_i$单增，所以凸壳左端点必为最优决策。
决策的舍弃 (r)
当前的$i$转移完后，要将其加入单调队列以便$i+1$选择决策。要维护下凸包，就必须让单调队列里的$k$单调递增。
如图，新增点与$C$连线可以满足下凸包性质(选这个点比$D,E$截距更小，答案更优)，所以$D,E$两点要舍弃
如果在单调队列中，$k_{q_rq_{r-1}} > k_{q_rq_{i}}$，那么就要舍弃$r$.
因为$x$坐标单增，所以新决策一定在凸壳右边。
代码
例题：Bzoj 1010
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
#include<queue>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
using namespace std;
LL n, P, dp[50005], s[50005];
LL l, r, que[150005];
inline db getK(int k, int j) {return (db)(dp[k] - dp[j] + (s[k] + P) * (s[k] + P) - (s[j] + P) * (s[j] + P)) / (2.0 * (db)(s[k] - s[j]));}
//计算两个点之间斜率
void clean() {}
int solve() {
clean();
scanf("%lld%lld", &n, &P), s[0] = 0, P++;
for (int i = 1; i <= n; i++) scanf("%lld", &s[i]), s[i] += s[i - 1];
for (int i = 1; i <= n; i++) s[i] += i;
dp[1] = 0, l = 1, r = 1; //原点是决策点 r必须为1
for (int i = 1; i <= n; i++) {
while (l < r && getK(que[l], que[l + 1]) <= (db)s[i]) l++;
//l必须严格小于r，因为单调队列中要有两个元素
dp[i] = dp[que[l]] + (s[i] - s[que[l]] - P) * (s[i] - s[que[l]] - P);
while (l < r && getK(que[r - 1], que[r]) >= getK(que[r], i)) r--;
que[++r] = i;
}
printf("%lld\n", dp[n]);
return 0;
}
int main() {
solve();
return 0;
}
易错点：
1、que[l]和l区别
2、原点是决策点 初始化r必须为1
3、单调队列中要有两个元素才能算斜率，所以l < r
4、斜率优化实数会被卡精度，用叉积来判，用叉积斜率必须大减小！
5、用叉积斜率必须大减小！否则不等式变号！
6、可以适当用数组简化一些东西
数的方法求斜率
我们设$i$前有两个决策$j, k(j < k)$, 且决策$k$比$j$优，则
$$dp(j)-2S_i(S_j+P)+(S_j+P)^2 > dp(k)-2S_i(S_k+P)+(S_k+P)^2$$
将包含$i$的移到左边，其他移到右边
$$-2S_i(S_j+P)+2S_i(S_k+P) > dp(k)-dp(j)-(S_j+P)^2+(S_k+P)^2$$
把左边$S_i$提取出来，再把提取出来的式子除到右边($S_i-S_j > 0$)
$$S_i > \frac{dp(k)+(S_k+P)^2-dp(j)+(S_j+P)^2}{2(S_k-S_j)}$$
令$k_{jk}=\frac{dp(k)+(S_k+P)^2-dp(j)+(S_j+P)^2}{2(S_k-S_j)}$，则满足$S_i > k_{jk}$时在$i$处时$k$比$j$优。
总结
斜率优化就是用来解决DP方程中有像$(a_i-a_j)^2$这样与$i, j$都相关的信息的优化，并且满足决策单调性，能够化作斜率式，并且斜率和$x$是单调的。如果斜率不是单调的，就要用二分查找队列中的最优解。如果$x$不是单调的，我们需要使用CDQ分治或者splay来解决这个问题。
斜率横坐标不单增
例题：Bzoj 2726
这里斜率横坐标不单增，所以凸壳左端点不一定为最优决策。
因为对于一条斜率为$k$的直线，将他放到凸壳中的应该排的位置即为最优决策点，所以我们可以不在队首淘汰元素，而是维护整个凸壳，然后在队列里二分找到将他放到凸壳中的应该排的位置即可转移。
