Meaning
很多时候的 (dp) ，大概都是一个这样的式子：
虽然普通决策单调性很好用是没错吧 = = ，但是对于有些题来说，首先 (cost) 函数不一定满足四边形不等式，其次决策单调性只适用于取 (Min) 的题目，再次决策单调性总要带个 (log) ，有时还不是最优秀的解法。
那么由数形结合衍生出来的决策单调性的一个分支就出来了：斜率优化。
对于斜率优化的题目，都满足决策单调性的 (g[i]ge g[i-1]) 。不过我们可以做到 (O(1)) 取得决策点 。
General
那么如何优化呢？很简单，从 (cost) 函数下手，我们设两个决策点 (j,k) 且有 (j>k) ，那么我们判断在什么情况下选 (j) 比选 (k) 更优。
即 (f[j]+cost[i,j]le orge f[k]+cost[i,k]) ，在这种情况下，我们将 (cost) 函数展开，一般情况下 (cost) 函数总是带着和 (i) 有关的项，我们将这些项全部移到一边，其他项移到不等式另一边，再将系数除过去，那么就会得到一个等式：某个与 (i) 有关的函数 (le) (frac{Sth}{Other things}) 。
接着我们发现右边的式子的求法就像斜率一样，那么可知，当两个决策之间满足这个不等式的时候，选 (j) 会比选 (k) 更优。则我们 (dp) 时可以维护一个单调队列，队列中相邻两项的斜率递增或递减，具体根据不等式另一边的函数递增还是递减。
这样讲还是讲不清楚的，结合具体题目来看最好。
Example1-[CEOI2004]锯木厂选址
Problem
有 (n) 颗树，它们在一条直线上顺序分布，(d[i]) 为第 (i) 棵树到第 (i+1) 棵树的距离，(w[i]) 为每棵树的重量，(d[n]) 是第 (n) 棵树到旧锯木厂的距离。要求选定两个位置建造新锯木厂，每棵树都会运到右边离它最近的锯木厂。
总花费为每棵树的重量×它到右边最近锯木厂的距离之和 。
(nle 20000) 。
First Mentality
首先观察到一个异常显然的伪 (dp) ：设 (f[i]) 为在第 (i) 棵树建造第二所新锯木厂的最小花费，(tot) 为不建造锯木厂的总花费，(dis[i]) 为 (i) 到旧锯木厂的距离，(q[i]) 为 (w) 的前缀和，则有：
答案则是 (Min(dp[i])) 。
但是 (n^2) 的复杂度显然要蛋糕。
斜率优化
我们发现，如果有 (j>k) ，且从 (j) 转移过来要比 (k) 更优，那么意味着有如下不等式：
通过移项得到：
则如果 (j) 与 (k) 满足这个不等式的话，从 (j) 转移必定比从 (k) 转移更优。
由于我们枚举 (i) 的时候从左往右，则 (dis[i]) 是递减的，那么如果 (j) 与 (k) 的这个不等式当前时候满足了，之后的 (dp) 过程中也必定会满足。
所以这个 (dp) 满足决策单调性，且与之前的 (dp) 值无关，于是我们可以用决策单调性分治来做。
但是用决策单调性做太没技术含量了，毕竟 (O(nlog)<O(n)) ，我们来玩斜率优化吧。
对于每个点 (j) 我们可以看做二维平面上的一个横坐标为 (dis[j]*q[j]) ，纵坐标为 (q[j]) 的点，那么对于这个式子 (frac{dis[j]*q[j]-dis[k]*q[k]}{q[j]-q[k]}) ，我们可以理解为直线 (kj) 的斜率。
由于 (dis[i]) 是单调递减的，则我们对斜率的要求也是单调递减，那么我们用一个单调队列维护这些决策点，保证队列内的斜率单调递减就好了。
第一次接触斜率的话建议瞅瞅代码。
Code
(work(i,j)) 代表计算决策点 (i,j) 之间的斜率。
#include <cstdio>
#include <iostream>
using namespace std;
int n, head, tail, tot, Ans = 2e9, w[20001], d[20002], q[20002], que[20001];
double work(int a, int b) {
return 1.0 * (q[b] * d[b] - q[a] * d[a]) / (q[b] - q[a]);
}
int main() {
cin >> n;
for (int i = 1; i <= n; i++) scanf("%d%d", &w[i], &d[i]);
for (int i = n; i >= 1; i--) d[i] += d[i + 1];
for (int i = 1; i <= n; i++) q[i] = q[i - 1] + w[i], tot += w[i] * d[i];
for (int i = 1; i <= n; i++) {
while (head < tail && work(que[head], que[head + 1]) > d[i])
head++; //如果队首斜率满足要求，则 head+1 会优于 head
int x = que[head];
Ans = min(Ans, tot - q[x] * d[x] - d[i] * (q[i] - q[x]));
while (head < tail && work(que[tail - 1], que[tail]) < work(que[tail], i))
tail--; //单调队列保证斜率单调递减，则如果尾部斜率小于 i 的斜率，弹掉它
que[++tail] = i;
}
cout << Ans;
}
Example2-[SDOI2016]征途
Problem
给出一段序列，要求连续划分成 (m) 段，每一段的值为段内元素之和。
要求使这 (m) 段的方差最小，输出最小方差×(m^2) 的值。
(mle nle3000)
First Mentality
我们划分成 (m) 段，设第 (i) 段的值表示为 (a_i) ，平均数表示为 (average) ，首先我们来看看方差的式子：
一看就很仙，我们还是先化化简吧，我们的答案还要乘上 (m^2) ，目的就是为了使结果为整数，那么我们化简成不带分数的形式总是没错的 (QwQ) 。
接下来由于总共有 (m) 段，我们把 (sum) 里的定项拆出来。
然后我们把 (average) 展开，并设 (sum a_i=sum) ，则 (average=frac{sum}{m}) 写成正常的式子：
然后减去同类项就行了：
那么式子就化简完了，由于 (sum^2) 和 (m) 都是个定值，所以我们还是只要关心 (sum a_i^2) 最小就行了。
那么思路很明显了：设 (f[i][j]) 为选到第 (i) 个数，已经划分成了 (j) 段的最小值，设第 (i) 位的前缀和为 (q[i]) 那么不难想到方程如下：
不过这样转移是 (n^3) 的，有待优化。
斜率优化
熟悉的套路的推式子环节来啦！
首先嘛，我们发现 (f[i][j]) 的转移只与 (f[k][j-1]) 有关，那么我们可以用 (f[i]) 表示目前第 (j) 层的 (dp) 值，(g[i]) 表示第 (j-1) 层的 (dp) 值，滚动优化一下空间。
设从 (j) 转移比从 (k) 转移更优，且 (j>k) ，则有：
展开平方并移项：
那么最后我们得到了这个快乐的斜率式。
由于 (q[i]) 递增，那么这个 (dp) 就符合决策单调性，(j) 点一时优，那么就永远优于 (k) ，我们设 (s[i]) 为 (f[i]) 的最优决策点，那么显而易见的 (s[i]ge s[i-1]) ，辣么由于转移的式子与 (f[j]) 无关，我们还是可以用决策单调性分治， 我们就自由了很多。
所以维护一个斜率递增的单调队列就行。
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
int n, m, head, tail, a[3001], que[3001];
long long q[3001], f[3001], g[3001];
long double work(int a, int b) {
return 1.0 * (q[b] * q[b] + g[b] - q[a] * q[a] - g[a]) /
(2 * q[b] - 2 * q[a]);
}
int main() {
cin >> n >> m;
for (int i = 1; i <= n; i++) {
scanf("%d", &a[i]);
q[i] = q[i - 1] + a[i], g[i] = q[i] * q[i];
}
for (int j = 2; j <= m; j++) {
head = tail = 1;
que[head] = j - 1;
for (int i = j; i <= n; i++) {
while (head < tail && work(que[head], que[head + 1]) < q[i]) head++;
int x = que[head];
f[i] = g[x] + (q[i] - q[x]) * (q[i] - q[x]);
while (head < tail && work(que[tail - 1], que[tail]) > work(que[tail], i))
tail--;
que[++tail] = i;
}
for (int i = 1; i <= n; i++) g[i] = f[i];
}
cout << 1ll * f[n] * m - q[n] * q[n];
}