算法学习笔记(3)：与斜率优化共舞

斜率优化 DP

对于像如下这样的 dp 方程，我们可以使用斜率优化解决。

[dp_i = min / max { a_i times b_j + c_i + d_j } ]

---

例题：P2900 Land Acquisition G

显然，如果 (w_i ge w_j) 且 (l_i ge l_j)，那么土地 (j) 可以直接被土地 (i) 并购。

考虑将所有土地按 (w_i) 降序排序，(w_i) 相同的按 (l_i) 降序排序，再通过双指针保留不能被其它土地并购的土地。

注意到此时被保留下的土地，(w_i) 满足 单调递减，(l_i) 满足 单调递增。

令 (dp_i) 表示将第 (1 sim i) 块土地并购的最小代价，不难列出 dp 方程：

[dp_i = min_{0 le j < i} { dp_j + w_{j + 1} times l_{i} } ]

上面的方程复杂度为 (O(n^2))，然而 (n leq 5 times 10^4)，我们需要想办法优化。

先将 (min) 去掉，再把 (w_{j + 1} times l_{i}) 移到左边，得：

[-w_{j + 1} times l_i + dp_i = dp_j ]

将所有能够转移到 (i) 的 (j) 视为一个点 ((-w_{j + 1}, dp_j))，那么问题就转化成了：

• 有一条斜率为 (l_i) 的直线，这条直线需要经过上述的这些点中的一个或多个，并且希望它的截距最小。

上面这句话有点抽象，不妨将 原方程 与 一次函数 做一个对比，发现它们确实十分相似：

[textcolor{red}{-w_{j + 1}} times textcolor{blue}{l_i} + textcolor{green}{dp_i} = textcolor{orange}{dp_j} ]

[newline textcolor{red}{k}textcolor{blue}{x} + textcolor{green}{b} = textcolor{orange}{y} ]

本质就是我们拿着一条斜率为 (l_i) 的直线，从下往上靠（增加它的截距），直到某一时刻这条线经过了我们维护的一个或多个点，停下来，此时截距（(dp_i)）一定是最小的。

仔细观察可以发现，无论斜率 ((l_i)) 是多少，有些点一定不会被第一次经过（如下图灰色点）。将这些点去除，剩余的点恰好形成了一个右下凸壳：

不妨先来维护这个凸壳，假设现在加入点 (C(-w_{i + 1}, dp_i))，考虑凸壳上最新的两个点 (A) 和 (B)，只可能有以下两种情况：

• (C) 点可以直接加入凸壳。

记点 (X) 与点 (Y) 所连成的直线斜率为 (text{slope}(X, Y))，则 (C) 能直接加入凸壳当且仅当 (text{slope}(A, B) leq text{slope}(B, C))。

• (C) 点加入后无法形成凸壳。

这时候一定有 (text{slope}(A, B) geq text{slope}(B, C))，故需要将 (B) 弹出凸壳，在拿剩余凸壳最新的两个点与 (C) 作比较。

由于这些点的 (x) 单调递增，可以使用类似单调栈的方法维护，时间复杂度 (O(n))。

接下来就是要在维护出的凸壳上找到最优决策点，随便画一张图，由于这些直线的斜率一定不断增加，所以最优决策点一定不断向凸壳上方移动：

进一步观察，可以发现，如果凸壳上相邻的两点 (A) 和 (B) 满足 (text{slope}(A, B) leq l_i)，那么点 (B) 永远在 (i) 以后一定 不会成为最优决策点。不妨把原来维护凸壳的单调栈换成单调队列，通过凸壳最前面两点的斜率判断是否弹出队头。最终，队头一定是当前的最优决策点。

时间复杂度 (O(n))（本题由于要排序所以总复杂度应该为 (O(n log n))，这里只计算了 dp 的复杂度）。代码如下：

#include <bits/stdc++.h> using namespace std; int n, pos, q[50005], h, t; long long dp[50005]; struct land {   int w, l;   bool operator<(const land t) const   {     return w == t.w ? l > t.l : w > t.w;   } } p[50005];  double X(int j) {   return -p[j + 1].w; }  double Y(int j) {   return dp[j]; }  double slope(int x, int y) {   return (Y(x) - Y(y)) / (X(x) - X(y)); }  int main() {   scanf("%d", &n);   for (int i = 1; i <= n; i++)     scanf("%d%d", &p[i].w, &p[i].l);   sort(p + 1, p + n + 1);   for (int i = 1; i <= n; i++)     if (p[i].l > p[pos].l)       p[++pos] = p[i];   for (int i = 1; i <= pos; i++)   {     while (h < t && slope(q[h], q[h + 1]) <= p[i].l)       h++;     dp[i] = dp[q[h]] + p[q[h] + 1].w * 1LL * p[i].l;     while (h < t && slope(q[t - 1], q[t]) >= slope(q[t], i))       t--;     q[++t] = i;   }   printf("%lld", dp[pos]);   return 0; } 

---

例题：P3195 玩具装箱

记 (s_i = sum_{j=1}^i C_i)，则可以列出 dp 方程：

[dp_i = min_{0 le j < i} { dp_j + (s_i - s_j + i - j - 1 - L)^2 } ]

令 (a_i = s_i + i - 1 - L, b_i = s_j + j)，原方程变为

[dp_i = min_{0 le j < i} { dp_j + (a_i - b_j)^2 } ]

即

[dp_i = min_{0 le j < i} { dp_j - 2a_ib_j + b_j^2 } + a_i^2 ]

将 (min) 及其以外得东西去掉，得

[dp_i = dp_j - 2a_ib_j + b_j^2 ]

化为直线的形式

[2a_ib_j + dp_i = dp_j + b_j^2 ]

类似与之前的形式，把每个 (j) 视作点 ((b_j, dp_j + b_j^2))，每次直线的斜率为 (2a_i)，做斜率优化即可。

#include <bits/stdc++.h> using namespace std; typedef long long ll; int n, L, C, h, t, q[50005]; ll s[50005], dp[50005];  double X(int j) {   return s[j] + j; }  double Y(int j) {   return (s[j] + j) * (s[j] + j) + dp[j]; }  double slope(int i, int j) {   return (Y(i) - Y(j)) / (X(i) - X(j)); }  int main() {   scanf("%d%d", &n, &L);   for (int i = 1; i <= n; i++)   {     scanf("%d", &C);     s[i] = s[i - 1] + C;   }   h = t = 1;   for (int i = 1; i <= n; i++)   {     while (h < t && slope(q[h], q[h + 1]) <= 2 * (s[i] + i - L - 1))       h++;     dp[i] = dp[q[h]] + sq(s[i] - s[q[h]] + i - q[h] - 1 - L);     while (h < t && slope(q[t - 1], q[t]) >= slope(q[t], i))       t--;     q[++t] = i;   }   printf("%lld", dp[n]);   return 0; } 

---

例题：P5785 任务安排（弱化版 P2365 任务安排）

至于方程是如何提前计算贡献的我就不细说了，记 (text{sumT}_i = sum_{j=1}^i T_i,text{sumC}_i = sum_{j=1}^i C_i)，可列出方程：

[dp_i = min { dp_j + text{sumT}_i times (text{sumC}_i - text{sumC}_j) + s times (text{sumC}_n - text{sumC}_j) } ]

展开整理成直线形式，即

[(text{sumT}_i + s) times text{sumC}_j + dp_i = dp_j ]

每个 (j) 所代表的点：((text{sumC}_i, dp_j))，直线斜率 (text{sumT}_i + s)。

正准备敲板子的你突然发现了这一条限制：

[|T_i| leq 2^8 ]

也就是说

[-2^8 le T_i le 2^8 ]

那么 (text{sumT}_i + s) 就不单调了，就不能一味地弹出队头了！

可凸壳上相邻两点地斜率还是单调的啊！那么只需要在凸壳上二分，找决策点即可。

时间复杂度 (O(n log n))。

#include <bits/stdc++.h> using namespace std; long long n, s, sumT[300005], sumC[300005], dp[300005], top, stk[300005];  long long X(int j) {   return sumC[j]; }  long long long Y(int j) {   return dp[j]; }  int main() {   scanf("%lld%lld", &n, &s);   for (int i = 1; i <= n; i++)   {     long long t, f;     scanf("%lld%lld", &t, &f);     sumT[i] = sumT[i - 1] + t;     sumC[i] = sumC[i - 1] + f;   }   stk[++top] = 0;   for (int i = 1; i <= n; i++)   {     int l = 1, r = top - 1, pos = stk[top];     while (l <= r)     {       int mid = (l + r) >> 1;       if (Y(stk[mid + 1]) - Y(stk[mid]) > (sumT[i] + s) * (X(stk[mid + 1]) - X(stk[mid])))         pos = stk[mid], r = mid - 1;       else         l = mid + 1;     }     dp[i] = dp[pos] + sumT[i] * (sumC[i] - sumC[pos]) + s * (sumC[n] - sumC[pos]);     while (top > 1 && (Y(stk[top]) - Y(stk[top - 1])) * (X(i) - X(stk[top])) >= (Y(i) - Y(stk[top])) * (X(stk[top]) - X(stk[top - 1])))       top--;     stk[++top] = i;   }   printf("%lld", dp[n]);   return 0; } 

注：斜率优化比较时建议移项，把除法化为乘法；如果使用 double 类型的 slope 很可能会产生精度误差（本题就卡了。

---

斜率优化小结：

• 列出方程，先通过一些简单的代换化简成直线形式。

• 通过 (min / max) 以及 (X) 和 (Y) 坐标的单调性判断凸壳方向。

• 如果直线斜率不单调，使用二分维护。

• 如果 (Y) 坐标不单调，可以证明对最终凸壳没有影响。

• 如果 (X) 坐标不单调，可以考虑 (text{CDQ}) 分治解决，时间复杂度 (O(n log^2 n))。