前言
本文介绍了斜率优化 DP 的推导过程及其基础应用，如果想要有更多了解请自行查阅其它文章。
算法介绍
在平时的 DP 过程中，我们可能会遇到这样的 DP 式子：
单调队列优化 DP 拼劲全力无法战胜，只能请它大哥出场了。
推导一
动态规划当然要考虑最优决策点的位置呀！所以我们假设现在有 \(j_1,j_2(j_1<j_2)\) 两个决策点，如果 \(j_2\) 更优秀，应该满足的条件是酱紫的：
如果 \(b_{j_1}-b_{j_2}\ne 0\)，那么我们就会得到这个不等式：
如果 \(b_{j_1}-b_{j_2}=0\)，你可以认为上面那个值是 \(\infty\)。
这里我们令 \(X(i)=b_i,Y(i)=dp_{i}+d_{i}\)，那么不等式变为：
将 \((X(j),Y(j))\) 作为 \(j\) 的对应点放入平面。如果 \(j_1\) 与 \(j_2\) 构成的直线斜率小于等于 \(a_i\)（这里 \(j_1,j_2\) 作为决策点出现），那么 \(j_2\) 优于 \(j_1\)；否则 \(j_1\) 优于 \(j_2\)。
假设 \(j\in [i-x,i-y]\)，那么下图的点就是对应到平面上的散点：
我们把目光放到 \(A,B,C\) 三个点上，这里假设 \(A,B\) 构成的直线斜率是 \(k_1\)，\(B,C\) 构成的直线斜率是 \(k_2\)，此处我们钦定 \(k_1>k_2\)。
- 如果 \(k_2<k_1\le a_i\)，那么 \(C\) 是最优点
- 如果 \(k_2\le a_i<k_1\)，那么 \(C\) 是最优点
- 如果 \(a_i<k_2<k_1\)，那么 \(A\) 是最优点
也就是说，\(B\) 永远不会存为最优点，就要淘汰掉（太馋人，哦不太残忍了）。
同样的道理，这里看似有这么多点，但实则只有下凸包上的点会用到：
又因为下凸包的斜率是单调递增的，如果 \(j\) 前面的斜率都是小于等于 \(a_i\)，后面的斜率都是 \(>a_i\)，那么 \(j\) 就是当前的最优决策点。
那不对呀！上凸包怎么能被忽略呢？！
所以如果上面不等式是 \(a_i\le \frac{Y(j_1)-Y(j_2)}{X(j_1)-X(j_2)}\) 的话，那么决策点就在上凸包上啦！
推导二
TA 回来了：
先假装看不见 \(\min\)：
进一步：
令 \(y=dp_j+d_j,k=-a_i,x=b_j,b=dp_i-c_i-m\)，那么上式就变成了 \(y=kx+b\)，此时最小化 \(dp_i\) 就相当于最小化 \(b\)。
怎样移向呢？看法则：
- \(x,y\) 与 \(i\) 无关
- \(k,b\) 与 \(j\) 无关
- \(b\) 中要有我们要求的 \(dp_i\)
我们把每一个 \(x,y\) 当成一个点对应到平面上，这就是我们的决策点。接着我们用 \(k=-a[i]\) 的直线去对准每一个点（如图），看看哪条直线的截距（也就是 \(b\)）最小就好了。
你看，最优决策点的位置不变，说明最优决策点还是在下凸包的斜率单峰处。
当然，最大化 \(b\) 就是上凸包。
总结
其实它们本质是相同的，可以相辅相成地来理解。
接下来，明白了最优决策点在什么位置，那该怎么快速地找最优决策点呢？
- 如果状态转移决策具有决策单调性（放在刚才的例子里就是 \(\forall i>j,a_i>a_j\)，即二次项系数 \(a_i\) 单调递增，此时随着和斜率比较的 \(a_i\) 的不断增加，由于下凸包上的点单调递增，\(a_i\) 卡到下凸包上的点一定越来越靠后），则可以用单调队列维护凸包上的点（单调队列返厂啦！）。
- 如果不具有决策单调性，则根据凸包的单调性二分即可。
例题讲解
P3195 [HNOI2008] 玩具装箱
题目分析
- 状态设计：定义 \(dp_i\) 表示对于前 \(i\) 个玩具，若 \(i\) 作为所属分组的最后一个玩具，求总的最小花费。
- 转移方程：
\[dp_i=\min_{j=1}^{i-1}\{dp_j+(i-(j+1)+(\sum_{k=j}^i C_k)-L)^2\} \]设 \(S_i=\sum_{j=1}^i C_j,M=L+1\)，则转移方程变为：
\[dp_i=\min_{j=1}^{i-1}\{dp_j+(S_i-S_j-M)^2\} \]拆开：
\[dp_i=\min_{j=1}^{i-1}\{dp_j+S_i^2+S_j^2+M^2-2S_iS_j-2S_iM+2S_jM\} \]发现了 \(2S_iS_j\)，因此斜率优化必定了。
- 状态初始化：\(dp_0=0\)。
答案就是 \(dp_n\)。
如果当前状态为 \(dp_i\)，若存在决策点 \(j_1,j_2(j_1<j_2)\)，且 \(j_2\) 优于 \(j_1\)，则：
令 \(X(j) = S_j,\ Y(j) = dp[j] + S_j^2 + 2S_jM\)，得：
满足此条件时有 \(j_2\) 优于 \(j_1\)，则根据原理处的推导，只需要维护 \(j \in [1,i-1]\) 对应的点集 \((X(j),Y(j))\) 的下凸包即可。
又由于 \(S_i\) 单调递增，所以状态转移具有决策单调性，可以用单调队列维护，即不是 \(i\) 的最优决策点的点不会再是 \(i+1\) 的最优决策点。
注意：
- 单调队列中维护凸包上的点对应的 \(j\)。
- 维护的点不应存在三点共线，而应当只维护两端点。
- 单调队列中应保证至少有两个点再求斜率，
deque难以实现且常数大，建议使用手写队列。 - 维护凸包比较斜率时建议不要使用除法，容易被卡精度，交叉相乘是更好的选择。同时，\(\dfrac{a}{0} \ge \dfrac{b}{c}\) 交叉相乘后恒成立，这难道不正是我们一直在找的 \(\dfrac{a}{0} = \infty\) 的可行实现方案吗？
代码实现
#include <bits/stdc++.h>
#define int long long
using namespace std;const int N = 5e4 + 10;
int n, L, c[N];
int dp[N], s[N], a[N], b[N];
int q[N], h = 1, t = 1;
int X(int p) { return b[p]; }
int Y(int p) { return dp[p] + b[p] * b[p]; }
double slope(int a, int b) {if (X(a) == X(b)) {if (Y(a) == Y(b)) return 0; // 斜率无法比较if (Y(a) > Y(b)) return -1e18; // 斜率为负无穷else return 1e18; // 斜率为正无穷}return (Y(a) - Y(b)) * 1.00 / (X(a) - X(b));
}signed main() {scanf("%lld%lld", &n, &L);for (int i = 1; i <= n; i++) scanf("%lld", &c[i]), s[i] = s[i - 1] + c[i];for (int i = 0; i <= n; i++) a[i] = s[i] + i, b[i] = s[i] + i + L + 1;q[1] = 0;for (int i = 1; i <= n; i++) {// 由于凸包的斜率一定单调递增，于是把队头斜率小于 2 * a[i] 的点删除while (h < t && slope(q[h], q[h + 1]) <= 2 * a[i]) h++;int j = q[h];dp[i] = dp[j] + (a[i] - b[j]) * (a[i] - b[j]); // 状态转移方程// 把队尾的斜率小于当前点的坐标删除，放入当前点while (h < t && slope(q[t - 1], q[t]) >= slope(q[t], i)) t--;q[++t] = i;}printf("%lld\n", dp[n]);return 0;
}
P2365 [IOI 2002] 任务安排
题目分析
- 状态设计：用 \(dp_{i,j}\) 表示前 \(i\) 个任务分成 \(j\) 组，\(i\) 为第 \(j\) 组最后一个任务，完成所有任务所需时间的最小值。
- 转移方程：
\[\begin{aligned} dp_{i,j} &= \min_{j-1\le k<i} dp_{k,j-1} + \sum_{p=k+1}^{i} tim_j \times f_k+s \\ &= \min_{j-1\le k<i} dp_{k,j-1} + tim_j \times \sum_{p=k+1}^{i} f_k+s \end{aligned} \]优化一下，假设 \(T_i=\sum_{j=1}^i tim_j,F_i=\sum_{j=1}^i f_j\)。
则上式变为：\[dp_{i,j} = \min_{j-1\le k<i} dp_{k,j-1} + tim_j \times (F_i-F_k) \]
- 状态初始化：\(dp_{0,0}=0,dp_{0,i}=\infty(i\ge 1)\)
答案就是 \(\min\{dp_{n,j}(j\ge 1)\}\)。
一个完美的 \(\mathcal{O}(n^3)\) 的超时做法。
我们发现为了知道当前是第几组，我们耗费了一维空间去存储这个数据，所以可以考虑把这一维扔掉。
但是这样我们就不知道机器启动过几次了！
别慌，冷静分析一下你会发现，如果我们要从 \(dp_j\) 转移到 \(dp_i\) 的话，由于第 \(j+1\sim i\) 都是在同一组内完成的，我们只需要把 \(s\) 对 \(j+1\) 后的影响补充到费用中就可以了！
- 状态设计：用 \(dp_i\) 表示对于前 \(i\) 个任务，\(i\) 为当前分组最后一组的最后一个任务，完成所有任务所需时间的最小值。
- 转移方程：
\[dp_i = \min_{0\le j<i} \{dp_{j} + s\times(F_n-F_j) + T_i\times(F_i-F_j)\} \]
- 状态初始化：\(dp_{0}=0\)
答案就是 \(\min\{dp_{n}\}\)。
代码实现
#include <bits/stdc++.h>
#define maxn 5010
#define int long long
using namespace std;int n, s, sc[maxn], st[maxn], f[maxn];
signed main() {cin >> n >> s;for (int i = 1; i <= n; i++) cin >> st[i] >> sc[i];for (int i = 1; i <= n; i++) st[i] += st[i - 1], sc[i] += sc[i - 1];memset(f, 0x3f, sizeof(f));f[0] = 0;for (int i = 1; i <= n; i++)for (int j = 0; j < i; j++)f[i] = min(f[i], f[j] + s * (sc[n] - sc[j]) + st[i] * (sc[i] - sc[j]));cout << f[n] << endl;return 0;
}
P10979 任务安排 2
题目分析
状态转移方程中有含 \(i\) 项与含 \(j\) 项的乘积，斜率优化没跑了。
依旧扔掉 \(\min\) 并且拆开括号：
令 \(y = dp_j, k = T_i + s, x = F_j, b = dp_i - T_i \times F_i - s \times F_n\)，一定要保证 \(b\) 中不含关于 \(j\) 的项，因为这样才能将问题转化为最小化 \(b\)。
如果将 \(j\) 在平面中对应的点设为 \((x,y)\)，问题就转化成了拿斜率为 \(k\) 的线去对应每个点，最小化截距 \(b\)。
易知最优决策点是下凸包上最后一个斜率小于等于 \(k\) 的右端点。
在这道题中，\(tim_i \ge 1\)，所以 \(T_i\) 单调递增，进而 \(k = T_i + s\) 单调递增，如果下凸包上某两个点构成的直线的斜率已经不是 \(i\) 前面最大的小于等于 \(T_i + s\) 的斜率，由于 \(T_{i+1} + s > st[i]\)，所以该直线的右端点也不可能作为 \(i + 1\) 的最优决策点。这种特性使得本题可以使用单调队列在维护下凸包的同时维护 \(i\) 的最优决策点。
代码实现
#include <bits/stdc++.h>
#define N 300010
#define int long long
using namespace std;int n, s, l = 1, r = 1, q[N];
int c[N], tim[N], f[N];
int dy(int j, int k) { return f[j] - f[k]; }
int dx(int j, int k) { return c[j] - c[k]; }signed main() {scanf("%lld%lld", &n, &s);for (int i = 1; i <= n; i++) {scanf("%lld%lld", tim + i, c + i);tim[i] += tim[i - 1];c[i] += c[i - 1];}q[1] = 0;for (int i = 1; i <= n; i++) {while (l < r && dy(q[l + 1], q[l]) <= (tim[i] + s) * dx(q[l + 1], q[l])) l++;int j = q[l];f[i] = f[j] + tim[i] * (c[i] - c[j]) + s * (c[n] - c[j]);while (l < r && dy(i, q[r]) * dx(q[r], q[r - 1]) <= dy(q[r], q[r - 1]) * dx(i, q[r])) r--;q[++r] = i;}printf("%lld\n", f[n]);return 0;
}
P5785 [SDOI2012] 任务安排
题目分析
在这道题中，\(tim\) 可能为负，所以 \(T[i]+s\) 不具有单调性。我们就需要记下来 \(i\) 前面的点的下凸包上的所有点，根据凸包上斜率的单调性进行二分。
代码实现
#include <bits/stdc++.h>
#define N 300010
#define int long long
using namespace std;int n, s, h = 1, t = 0, q[N];
int c[N], tim[N], f[N];
int dy(int j, int k) { return f[j] - f[k]; }
int dx(int j, int k) { return c[j] - c[k]; }
int find(int i) {if (h == t) return q[h];int l = h, r = t, res = h;while (l <= r) {int mid = (l + r) >> 1;if (dy(q[mid + 1], q[mid]) <= dx(q[mid + 1], q[mid]) * (tim[i] + s)) l = mid + 1;else r = mid - 1, res = mid;}return q[res];
}signed main() {scanf("%lld%lld", &n, &s);for (int i = 1; i <= n; i++) {scanf("%lld%lld", tim + i, c + i);tim[i] += tim[i - 1];c[i] += c[i - 1];}for (int i = 1; i <= n; i++) {while (h < t && dy(i - 1, q[t]) * dx(q[t], q[t - 1]) <= dx(i - 1, q[t]) * dy(q[t], q[t - 1])) t--;q[++t] = i - 1;int j = find(i);f[i] = f[j] + tim[i] * (c[i] - c[j]) + s * (c[n] - c[j]);}printf("%lld\n", f[n]);return 0;
}
参考资料
- 斜率优化 dp