来说一说斜率优化 dp。
定义
斜率优化可以优化形如 $dp_i=dp_j+val(j,i)$ 的 1d/1d 转移，其中 $val(j, i)$ 仅包含只有 $i$ 的任意次任意形式，$j$ 的任意次任意形式，$i,j$ 的任意形式的一次乘积项，不一定需要满足某种单调性。
通过简单的移项，得到形如 $y=k\cdot x+b$ 的形式，其中 $x,y$ 仅包含关于 $j$ 的项，$k,b$ 仅包含关于 $i$ 的项，以 $(x,y)$ 建立平面直角坐标系，发现 $dp_i$ 的最值就是以当前的 $i$ 位置的斜率 $k$ 关于若干个转移点 $p_j(x,y)$ 所截得的截距的最值。
说起来比较抽象，我们直接上题目。
题目
任务安排2
看到这道题目后，先考虑一个朴素的转移方程。
考虑记 $t$ 和 $c$ 的前缀和 $sumt$ 和 $sumc$，设 $dp_{i,j}$ 表示把前 $i$ 个任务分成 $j$ 批完成的最小费用。
则有
$dp_{i,j}=\min\limits_{0\le k<i} { dp_{k,j-1}+(S\times j+sumt_i)* (sumc_i-sumc_k) }$
时间复杂度 $\mathcal{O}(n^3)$，无法接受。
考虑为什么要设 $dp$ 的第二维，不难发现我们需要当前分的批数得出累积了多少次的启动时间来算贡献。
考虑到 $j$ 只对当前这一批的启动时间造成贡献，我们可以将当前这一批的启动时间同样累积到后续任务的代价中，且后续任务的总代价为定值，即 $sumc_n-sumc_j$ 那么我们可以去掉第二维。
设 $dp_i$ 表示完成前 $i$ 个任务的最小费用。
$dp_i=\min\limits_{0\le j < i}{dp_j+sumt_i*(sumc_i-sumc_j)+S*(sumc_n-sumc_j)}$
这种思想叫做费用提前计算，目的就是直接将为定值的贡献直接累积到最后，省略无用信息，时间复杂度 $O(n^2)$。
复杂度已经较优了，考虑斜率优化，适当将转移方程做一些变形。
$$dp_i=dp_j+sumt_i*(sumc_i-sumc_j)+S*(sumc_n-sumc_j)$$
$$\Rightarrow dp_i=dp_j+sumt_i* sumc_i-sumt_i* sumc_j+S* sumc_n-S*sumc_j$$
$$\Rightarrow dp_j=(S+sumt_i)*sumc_j+dp_i-sumt_i*sumc_i-S*sumc_n$$
这是一个一次函数 $y=k\cdot x+b$，其中 $ y=dp_j, x=sumc_j, k=S+sumt_i, b=dp_i-sumt_i*sumc_i-S*sumc_n $，正好满足斜率优化的形式。
我们将每个决策 $j$ 看作平面直角坐标系的一个点 $(x,y)$，因为求 $dp_i$ 的最小值就是求截距的最小值，所以我们以斜率为 $k$ 的直线，从下往上所触碰到的第一个点，此时的截距即可得出 $dp_i$ 的最小值。
不难发现 $sumc_j$ 单调递增，即 $j$ 越大，它在平面直角坐标系的横坐标就越大，即插入点依次为从左到右。
我们去考虑相邻的三个点，在什么情况下位于中间的点能够造成贡献。
注：这里造成贡献的定义为，存在一个斜率为 $k$ 的直线可以截取到这个点。
我们考虑将第 $1$ 个点和第 $3$ 个点连线，讨论 $2$ 号点在这条线上方还是下方：
- $2$ 号点在直线上方
- $2$ 号点在直线下方
所以我们得出， 当 $\dfrac{y_2-y_1}{x_2-x_1}< k< \dfrac{y_3-y_2}{x_3-x_2}$ 且 $2$ 号点在直线下方才有可能作出贡献，以斜率作为比较就是 $\dfrac{y_2-y_1}{x_2-x_1}< \dfrac{y_3-y_2}{x_3-x_2}$，即维护一个斜率单调递增的下凸壳，这是一个十分有用的条件！加上此题的 $sumt_i$ 单调递增，我们也有了 $k$ 为单调递增的条件，那么我们只需维护一个单调队列，在取出队头两个点所形成的直线的斜率，如果已经小于等于 $k$，我们一定不会以队头作为最优决策且以后也不会，弹出队头并继续更新。对于当前进入队尾的决策点 $j$，如果斜率小于等于当前队尾两个点的斜率，那么就一直弹出，最后插入决策 $j$。
应该还不是太难以理解吧。
任务安排3
与上一题不同，$t$ 可以为负数，即 $sumt$ 不一定单调递增，那么 $k$ 就不一定单调递增。
考虑 $k$ 单调递增对我们呢带来什么好处，就是可以让我们及时退出单调队列队头的决策点，那么如果没有这个条件，我们就可以不退这些决策点，维护当前的所有的 $(1\sim i-1)$ 下凸壳决策点集，然后以 $k$ 为斜率在里面二分取得最优决策点 $j$ 即可。
CF311B Cats Transport
也是道斜率优化的裸题。
考虑对每一只猫求一个启动时间 $t_i$，即只要铲屎官在 $t_i$ 时刻及以前出发，就可以接到这只猫。（原题的 $t$ 在这就没用处了）
将 $t$ 排序后得知，每位铲屎官所取得的猫一定是连续的一段，记 $sumt$ 为 $t$ 的前缀和。
设 $dp_{i,j}$ 表示前 $i$ 只猫使用 $j$ 位铲屎官的最小代价。
则有 $dp_{i,j}=\min\limits_{0\le k<i}{dp_{k,j-1}+(i-k)*t_i-(sumt_i-sumt_k)}$
简单变形后得到：$dp_{k,j-1}+sumt_k=t_i*k+dp_i-t_i*i+sumt_i$，符合斜率优化的形式。
不难发现此题的斜率 $k$ 随着 $i$ 增加仍然单调不减，且横坐标 $x$ 也为单调递增，故还可沿用任务安排2中的做法。
时间复杂度 $\mathcal{O}(n+mp)$。
代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 100005;
const int maxp = 105;
const ll Lnf = 0x3f3f3f3f3f3f3f3fll;
int read() {
int res = 0, ch = getchar();
while(!(ch >= '0' && ch <= '9') && ch != EOF) {
ch = getchar();
}
while(ch >= '0' && ch <= '9') {
res = (res << 3) + (res << 1) + (ch - '0');
ch = getchar();
}
return res;
}
ll n, m, p;
ll sumd[maxn], t[maxn];
ll q[maxn], head, tail;
ll sumt[maxn], dp[maxn][maxp];
int x(int k) {
return k;
}
ll y(int k, int j) {
return dp[k][j] + sumt[k];
}
int main() {
n = read(), m = read(), p = read();
for(int i = 2;i <= n;i++) {
int d = read();
sumd[i] = sumd[i - 1] + d;
}
for(int i = 1;i <= m;i++) {
int h = read(), x = read();
t[i] = x - sumd[h];
}
sort(t + 1, t + m + 1);
for(int i = 1;i <= m;i++) {
sumt[i] = sumt[i - 1] + t[i];
}
memset(dp, 0x3f, sizeof(dp));
dp[0][0] = 0;
for(int j = 1;j <= p;j++) {
head = 1, tail = 0;
q[++tail] = 0;
for(int i = 1;i <= m;i++) {
while(head < tail && (y(q[head + 1], j - 1) - y(q[head], j - 1)) <= t[i] * (x(q[head + 1]) - x(q[head]))) head++;
dp[i][j] = dp[q[head]][j - 1] + 1ll * (i - q[head]) * t[i] - (sumt[i] - sumt[q[head]]);
if(y(i, j - 1) >= Lnf) continue;
while(head < tail && (y(i, j - 1) - y(q[tail], j - 1)) * (x(q[tail]) - x(q[tail - 1])) <= (y(q[tail], j - 1) - y(q[tail - 1], j - 1)) * (x(i) - x(q[tail]))) tail--;
q[++tail] = i;
}
}
printf("%lld\n", dp[m][p]);
return 0;
}
P5017 [NOIP2018 普及组] 摆渡车
这道题还是过于经典了，今天我们来阐述 $\mathcal{O}(T+m)$ 的斜率优化做法。这里 $T$ 是 $t_i$ 的最大值。
开始一直在想严格 $\mathcal{O}(n)$ 的做法，但斜率优化好像不行，就改设另外的 $dp$ 状态了。
记 $sum_i$ 表示来的时刻在 $[1,i]$ 的有多少人，$sumt_i$ 表示来的时刻在 $[1,i]$ 的时刻之和。
不难想到每次摆渡车所接的人肯定是按时刻排序后连续的一段人，设 $dp_i$ 表示接完 $[1,i]$ 时刻来的人的最小等待时间。
则有方程： $dp_i=\min\limits_{0\le j\le \max(i-m,0)}{dp_j+(sum_i-sum_j)* i - (sumt_i-sumt_j)}$
当 $i-m<0$ 时，$dp_i=sum_i*i-sumt_i$。
我们继续变换式子，得到：$dp_j+sumt_j=i*sum_j+dp_i-sum_i*i+sumt_i$
观察斜率和横坐标仍然单调递增，故继续使用任务安排2的做法即可。
P3628 [APIO2010]特别行动队
这题已经说了取连续的一段人算代价了，故还可设 $dp_i$ 为前 $i$ 个人的最大战斗力。
令 $sumx$ 为 $x$ 的前缀和。
转移方程： $dp_i=\min\limits_{0\le j<i}{dp_j+a*(sumx_i-sumx_j)^2+b*(sumx_i-sumx_j)+c}$
提供 $i,j$ 的乘积项，有且仅在 $a*(sumx_i-sumx_j)^2$ 中提供 $-2a\cdot sumx_i\times sumx_j$，那么此题中的 $k=-2a\cdot sumx_i,x=sumx_j$。
（现在你也应该可以发现，当 $dp$ 方程转化成斜率优化的形式后，只有 $k,x$ 还在起作用）
与前几道题不同的是，本题的 $x$ 为单调递增，但 $k$ 却为单调递减且为负值，会不会对我们维护的东西产生影响？
这里我们不在举例解释，最终我们要维护一个斜率单调递减的上凸壳，感兴趣的读者自行画图理解。
在判掉队头的斜率时，也同样要变号，即：如果队头的两个决策点组成的直线大于等于 $k$，我们就不会以它为最优决策，弹掉队头然后继续比较。
代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1000005;
int read() {
int res = 0, f = 1, ch = getchar();
while(!(ch >= '0' && ch <= '9') && ch != EOF) {
if(ch == '-') {
f = -1, ch = getchar();
}
else ch = getchar();
}
while(ch >= '0' && ch <= '9') {
res = (res << 3) + (res << 1) + (ch - '0');
ch = getchar();
}
return res * f;
}
ll n, a, b, c;
ll q[maxn], head, tail;
ll sumx[maxn], dp[maxn];
ll x(int j) {
return sumx[j];
}
ll y(int j) {
return dp[j] + a * sumx[j] * sumx[j] - b * sumx[j];
}
int main() {
n = read(), a = read(), b = read(), c = read();
for(int i = 1;i <= n;i++) {
int f = read();
sumx[i] = sumx[i - 1] + f;
}
memset(dp, ~0x3f, sizeof(dp));
dp[0] = 0;
head = 1, tail = 0;
q[++tail] = 0;
for(int i = 1;i <= n;i++) {
while(head < tail && y(q[head + 1]) - y(q[head]) >= 2 * a * sumx[i] * (x(q[head + 1]) - x(q[head]))) head++;
dp[i] = dp[q[head]] + a * sumx[i] * sumx[i] + a * sumx[q[head]] * sumx[q[head]] - 2 * a * sumx[i] * sumx[q[head]] + b * sumx[i] - b * sumx[q[head]] + c;
while(head < tail && (y(i) - y(q[tail])) * (x(q[tail]) - x(q[tail - 1])) >= (y(q[tail]) - y(q[tail - 1])) * (x(i) - x(q[tail]))) tail--;
q[++tail] = i;
}
printf("%lld\n", dp[n]);
return 0;
}
P3195 [HNOI2008]玩具装箱
记 $sumc$ 为 $c$ 的前缀和。
设 $dp_i$ 表示前 $i$ 个玩具的最小花费。
则有方程：$dp_i=\min\limits_{0\le j<i}{dp_j+(i-j-1+sum_i-sum_j-L)^2}$。
我们令 $p=i-1-L,q=sum_j+j$，
$$\Rightarrow dp_i=dp_j+(p-q)^2$$
$$\Rightarrow dp_i=dp_j+p^2-2p\cdot q+q^2$$
$$\Rightarrow dp_j+q^2=2p\cdot q+dp_i-p^2$$
其中 $k=2p=2\times(i-1-L),x=q=sum_j+j$，即 $k$ 与 $x$ 都为单调递增，用单调队列维护下凸壳即可。
P2497 [SDOI2012]基站建设
列出转移方程：$dp_i=\min\limits_{1\le j<i}{dp_j+\dfrac{x_i-x_j}{2\sqrt{r_j}}}+v_i$，其中 $dp_1=v_1$。
移项：$dp_j-\dfrac{x_j}{2\sqrt{r_j}}=(-x_i)\times \dfrac{1}{2\sqrt{r_j}}+dp_i-v_i$
我们发现，斜率 $k$ 单调递减，也就是维护上凸壳，但 $x$ 却没有单调性，这时候我们考虑 CDQ 分治。
考虑用 $[l,mid]$ 去更新 $[mid+1,r]$，先将 $[l,mid]$ 按 $r$ 归并排序，这样我们插入时就可以按横坐标顺序插入凸包，而 $[mid+1,r]$ 就先不用排序，因为我们需要使用斜率 $k$ 的单调性去维护凸包，最终实现的时间复杂度即为 $\mathcal{O}(n\log n)$。
代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double lf;
const int maxn = 500005;
ll read() {
ll res = 0, ch = getchar();
while(!(ch >= '0' && ch <= '9' && ch != EOF)) {
ch = getchar();
}
while(ch >= '0' && ch <= '9') {
res = (res << 3) + (res << 1) + (ch - '0');
ch = getchar();
}
return res;
}
ll n, m;
ll p[maxn], r0[maxn], v[maxn], id[maxn];
ll seq[maxn];
ll q[maxn], head, tail;
lf dp[maxn];
lf ans = 1e15;
lf x(int j) {
return 1.0 / (2.0 * sqrt(r0[j]));
}
lf y(int j) {
return dp[j] - (lf)(p[j]) / (2.0 * sqrt(r0[j]));
}
void solve(int l, int r) {
if(l == r) {
return;
}
int mid = (l + r) >> 1;
solve(l, mid);
head = 1, tail = 0;
for(int i = l;i <= mid;i++) {
while(head < tail && (y(id[i]) - y(q[tail])) / (x(id[i]) - x(q[tail])) >= (y(q[tail]) - y(q[tail - 1])) / (x(q[tail]) - x(q[tail - 1]))) tail--;
q[++tail] = id[i];
}
for(int i = mid + 1;i <= r;i++) {
while(head < tail && (y(q[head + 1]) - y(q[head])) / (x(q[head + 1]) - x(q[head])) >= -p[i]) head++;
dp[i] = min(dp[i], dp[q[head]] + (lf)(p[i] - p[q[head]]) / (2 * sqrt(r0[q[head]])) + v[i]);
}
solve(mid + 1, r);
int pos1 = l, pos2 = mid + 1, pos = l - 1;
while(pos1 <= mid && pos2 <= r) {
if(r0[id[pos1]] <= r0[id[pos2]]) {
seq[++pos] = id[pos1], pos1++;
}
else {
seq[++pos] = id[pos2], pos2++;
}
}
for(int i = pos1;i <= mid;i++) {
seq[++pos] = id[i];
}
for(int i = pos2;i <= r;i++) {
seq[++pos] = id[i];
}
for(int i = l;i <= r;i++) {
id[i] = seq[i];
}
}
int main() {
n = read(), m = read();
for(int i = 1;i <= n;i++) {
p[i] = read(), r0[i] = read(), v[i] = read();
id[i] = i;
}
for(int i = 0;i <= n;i++) {
dp[i] = 1e15;
}
dp[1] = v[1];
solve(1, n);
for(int i = 1;i <= n;i++) {
if(p[i] + r0[i] >= m) {
ans = min(ans, dp[i]);
}
}
printf("%.3Lf\n", ans);
return 0;
}
P2305 [NOI2014] 购票
树上斜率优化，还是有一定的难度。
设 $dp_u$ 表示从 $u$ 点走到 $1$ 点的最小费用。
则转移方程为： $dp_u=\min\limits_{fa\in anc_u,dep_u-dep_{fa}\le l_u}{dp_{fa}+p_u*(dep_u-dep_{fa})+q_u}$
稍微移一下项：$dp_{fa}=p_u*dep_{fa}+dp_u-p_u*dep_u-q_u$
这里的 $x$ 虽是单调递增，但斜率 $k$ 却没有单调性，所以我们需要把整个凸壳存下来然后二分，因为只用维护一头，我们可以采用单调栈存储。
但是在转移点的选择中还存在一个 $dep_u-dep_{fa}\le l_u$ 的限制，也就是每一个 $u$，它的转移点并不是 $1-u$ ，而有一个上限，那么我们就得尝试维护区间查询一个单调栈。
考虑到是树上问题，可能会有删除的操作，但我们不想写可撤销单调栈，怎么办。
这里有一种很好的 idea 叫做出栈序，我们先将树进行一遍 $dfs$，然后在退出这个节点时给它标号，有点后序遍历的感觉。
那么这是我们发现了一个神奇的性质，首先对于一个点 $u$，它的子节点所形成的若干个子树之间，两两之间的编号没有交集，这样我们在进行 $dfs$ 修改和查询时，不会查询到其它的子树上（尽管其它子树可能已经被修改），而查询的这条链的下方的节点，编号一定比整条链所有的编号要小，这条链上方的节点，编号一定比整条链所有的编号要大，这样我们在查询时，就能保证查的单调栈一定是只包含这条链的决策点的单调栈。
然后就比较好做了，维护一个线段树套单调栈，修改均摊 $\mathcal{O}(\log n)$，查询 $\mathcal{O}(\log^2 n)$。
总时间复杂度 $\mathcal{O}(n\log^2 n)$，空间复杂度 $\mathcal{O}(n\log n)$。
代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 200005;
const ll Lnf = 0x3f3f3f3f3f3f3f3fll;
ll read() {
ll res = 0, ch = getchar();
while(!(ch >= '0' && ch <= '9') && ch != EOF) {
ch = getchar();
}
while(ch >= '0' && ch <= '9') {
res = (res << 3) + (res << 1) + (ch - '0');
ch = getchar();
}
return res;
}
int n, t, top, head[maxn];
int dfn[maxn], node;
ll anc[maxn][20], dist[maxn][20], dep[maxn];
ll f[maxn], s[maxn], p0[maxn], q[maxn], l[maxn];
ll dp[maxn];
struct Edge {
int v;
ll w;
int next;
}Edge[maxn];
void insert(int u, int v, ll w) {
Edge[++top].v = v;
Edge[top].w = w;
Edge[top].next = head[u];
head[u] = top;
}
long double x(int fa) {
return dep[fa];
}
long double y(int fa) {
return dp[fa];
}
struct Stack {
vector<ll> stac;
Stack() {
stac.clear();
}
void add(int u) {
int cur = stac.size() - 1;
while(cur > 0 && (y(u) - y(stac[cur])) / (x(u) - x(stac[cur])) <= (y(stac[cur]) - y(stac[cur - 1])) / (x(stac[cur]) - x(stac[cur - 1]))) {
stac.pop_back(), cur--;
}
stac.push_back(u);
}
ll search(ll k) {
if((int)stac.size() == 0) return -1;
int l = 0, r = stac.size() - 1, mid;
while(l < r) {
mid = (l + r) >> 1;
if((y(stac[mid + 1]) - y(stac[mid])) / (x(stac[mid + 1]) - x(stac[mid])) <= k) {
l = mid + 1;
}
else {
r = mid;
}
}
return stac[l];
}
};
Stack tree[4 * maxn];
inline int ls(int p) {return p << 1;}
inline int rs(int p) {return p << 1 | 1;}
void update(int p, int l, int r, int x, int u) {
tree[p].add(u);
if(l == r) {
return;
}
int mid = (l + r) >> 1;
if(mid >= x) update(ls(p), l, mid, x, u);
else update(rs(p), mid + 1, r, x, u);
}
ll query(int p, int l, int r, int ql, int qr, int u) {
if(l == ql && r == qr) {
int fa = tree[p].search(p0[u]);
if(fa == -1) return Lnf;
else {
return dp[fa] + (dep[u] - dep[fa]) * p0[u] + q[u];
}
}
int mid = (l + r) >> 1;
if(mid >= qr) return query(ls(p), l, mid, ql, qr, u);
else if(mid + 1 <= ql) return query(rs(p), mid + 1, r, ql, qr, u);
else return min(query(ls(p), l, mid, ql, mid, u), query(rs(p), mid + 1, r, mid + 1, qr, u));
}
void dfs1(int u, int fa, ll lstw) {
anc[u][0] = fa, dist[u][0] = lstw, dep[u] = dep[fa] + lstw;
for(int k = 1;k < 20;k++) {
anc[u][k] = anc[anc[u][k - 1]][k - 1];
dist[u][k] = dist[anc[u][k - 1]][k - 1] + dist[u][k - 1];
}
for(int i = head[u];i;i = Edge[i].next) {
ll v = Edge[i].v, w = Edge[i].w;
dfs1(v, u, w);
}
dfn[u] = ++node;
}
int up(int u) {
ll v = u, sum = 0;
for(int k = 19;k >= 0;k--) {
if(anc[v][k] != 0 && sum + dist[v][k] <= l[u]) {
sum += dist[v][k], v = anc[v][k];
}
}
return v;
}
void dfs2(int u) {
if(u != 1) {
int fa = up(u);
dp[u] = query(1, 1, n, dfn[u], dfn[fa], u);
}
update(1, 1, n, dfn[u], u);
for(int i = head[u];i;i = Edge[i].next) {
int v = Edge[i].v;
dfs2(v);
}
}
int main() {
n = read(), t = read();
for(int i = 2;i <= n;i++) {
f[i] = read(), s[i] = read(), p0[i] = read(), q[i] = read(), l[i] = read();
insert(f[i], i, s[i]);
}
dfs1(1, 0, 0ll);
dfs2(1);
for(int i = 2;i <= n;i++) {
printf("%lld\n", dp[i]);
}
return 0;
}
总结
学个斜率优化总共用了也就 $1$ 周，但博客磨蹭了好久才写完。
大概几个月前，在刚翻开蓝书的斜率优化时，我对它还有一定的抵触心理，觉得自己应该看不懂。
但现在经过一个多小时的研究，最终也是能理解了书中的意思，自己找了几道题目也能够解出来，我认为还是达到了学习的效果和目的。
对于学习 OI，我们不能抱有太多逃避，不然你总是也学不会，只要肯努力，肯细心琢磨，才能理解的透彻。
话说我觉得我应该也只是理解了斜率优化的皮毛，如果还有更好的斜率优化题目，我也会及时在此更新。
下一步也不知道要新学点啥，要不定个四边形不等式？
这里奉劝大家：复习要及时，不然退役两行泪。