对于状态转移方程含有变量与常量的乘积项，并满足某些性质的 DP 的一类优化。

例题：HNOI2008

显然，可以得到一个 DP 的式子：

f(i) = \min_{j = 1}^{i - 1} \{ f(j) + (\sum_{k = j + 1}^{i} c_k + j - i - j - 1 - L)^2 \}

令 L \leftarrow L + 1, s(n) = \sum_{i = 1}^n c_i + i，可以得到：

f(i) = \min_{j = 1}^{i - 1} \{ f(j) + (s(i) - s(j) - L) ^ 2 \}

直接对这个式子进行模拟，时间复杂度为 O(n^2)，不能接受。

把这个 DP 式子当做一个方程，去掉 \min 展开来看：

f(i) = f(j) + (s(i) - L) ^ 2 + s(j) ^ 2 - 2 \times (s(i) - L) * s(j)

移项可以得到：

f(j) + s(j) ^ 2 = f(i) - (s(i) - L) ^ 2 + 2 \times (s(i) - L) * s(j)

如果将 s(j) 作横坐标，f(j) + s(j) ^ 2 看做纵坐标，则对于每一个已被计算过的，确定的 j，都可以在这个平面直角坐标系中找到唯一对应的点。而上面的方程可以看做：

y = kx + b

其中，y = f(j) + s(j) ^ 2, k = 2 \times f(s(i) - L), x = s(j), b = f(i) - (s(i) - L)^2。

也就是说，对于每个点，都有一条斜率相同（为 2 \times f(s(i) - l)）的直线穿过它，希望这个直线的纵截距（b）最小，因为这个截距是 f(i) - (s(i) - L) ^ 2，除了 f(i) 是要最小化的值以外，其他的都是确定的常量。

这是一个线性规划的问题，也可以理解为有一条斜率为 2 \times f(s(i) - L) 的直线从直角坐标系的极下处向上平移。显然，在这个平移的过程中，交到的第一个点即为所求。

有一个重要的结论，对于点 A, B，用一条斜率为 g 的直线从下向上平移，如果 \operatorname{slope}(A, B) < g 时，会先碰到 B，否则为 A。

一个重要的性质是，对于任意三个点，如果这个点是上凸的（斜率递减），则中间那个点，无论平移的直线斜率如何，都不可能是第一个遇到的。

在感性的验证若干次后，可以从数学上证明这个重要的事实：

\text{proof} :

令三个点依次为 (x1, y1), (x2, y2), (x3, y3)，记为点 A, B, C，记两点之间斜率为 \operatorname{slope}(A, B) = \dfrac{\Delta x}{\Delta y}。不妨设 x1 < x2 < x3。

因为上凸，所以有：

\operatorname{slope}(A, B) < \operatorname{slope}(B, C)

假设当平移直线斜率为 g 时，B 点会被优先交到。

则：

\operatorname{slope}(A, B) > G, \operatorname{slope}(B, C) < G

那么就应该有

\operatorname{slope}(A, B) > \operatorname{slope}(B, C)

与条件矛盾，故不存在这样的直线。

也就是说，可能的 j，在的直角坐标系上，两两之间斜率一定是单调递增的。

换而言之，所有可能的决策集合，在该平面直角坐标系上形成下凸包。

维护这个凸包，及时排除无效决策点，这就是斜率优化，也被称为凸包优化（convex hull）。

除此之外，本题还有若干在斜率优化中不平凡的性质：

  1. 对于横坐标 s(j)，随着 j 的递增，s(j) 也是递增的。这意味着在依次考虑每一个决策点时，都是有序的。
  2. 对于每条平移直线的斜率 2 \times s(i)，随着 i 的递增，2 \times s(i) 也是递增的。这意味着，在凸包中，当相邻两个点的斜率小于 2 \times s(i)，靠左（横坐标更小）的点在今后的 “平移” 过程中永远不会再被交到应当可以及时删去这些点。

要维护这样一个凸包，涉及到在某一端，根据某个值的大小进行删除，删除，使得在整个序列中都有单调性。

这就是单调队列所擅长的事了。

入队时，根据该点，队首的斜率与队首，队次首的斜率的大小关系比较即可。

由于本题满足平移直线斜率递增，故可以当队尾的斜率小于当前平移直线斜率时，将其抛出。

具体见代码。

时间复杂度 O(n)。

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef double db;

const int MAXN = 5e4 + 10;

int n;
ll L, t[MAXN], f[MAXN];

int q[MAXN], l, r;

db Y(int i) { return 1.0 * t[i] * t[i] + f[i]; }
db X(int i) { return 1.0 * t[i]; }
db slope(int i, int j) { return (Y(i) - Y(j)) / (X(i) - X(j)); }
db G(int i) { return 2.0 * (t[i] - L); }

int main() {
    scanf("%d %lld", &n, &L);
    L ++;
    for (int i = 1; i <= n; ++i) scanf("%lld", &t[i]);
    for (int i = 1; i <= n; ++i) t[i] += t[i - 1];
    for (int i = 1; i <= n; ++i) t[i] += i;
    q[1] = 0;
    l = 1, r = 1;
    for (int i = 1; i <= n; ++i) {
        while (l < r && slope(q[l], q[l + 1]) < G(i)) l ++;
        int j = q[l];
        f[i] = f[j] + (t[i] - t[j] - L) * (t[i] - t[j] - L);
        while (l < r && slope(q[r], i) < slope(q[r - 1], q[r])) r --;
        q[++ r] = i;
    }
    printf("%lld\n", f[n]);
    return 0;
}

其他题与做法

[USACO08MAR]Land Acquisition G

横坐标单调递减，维护下凸包，斜率单调递减。

首先将所有满足 w_i < w_j, l_i < l_j 的 i 全部删掉，这对答案没有贡献。

具体而言，以 w 为第一关键升序排序，l 为第二关键字升序排序。依次将元素压入一个单调栈中，如果栈顶的 l 小于当前元素的 l 就将栈顶弹出。可以发现剩下的就是那些对答案有贡献的元素（这貌似是一个新的求二维偏序的方法），而且此时，w 均单调递增，l 均单调递减。

令 f(i) 表示购买 [1, i] 的方案，可以得到:

f(i) = \min_{j = 1}^{i - 1} f(j) + w(i) * l(j + 1)

写成斜率优化的样子：

f(j) = f(i) - w(i) * l(j + 1)

发现斜率 -w(i) 递减，横坐标 l(j + 1) 递减，要使得函数纵截距最小，维护下凸包。

把 - 移到后面去，就变成了横坐标为 -l(j + 1)，递增，斜率 w(i)，递增。

就和例题一样的做法了。

时间复杂度 O(n))。

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double db;

const int MAXN = 5e4 + 10;

int n;

struct node { ll w, l; bool operator <(const node& b) { return w == b.w ? l < b.l : w < b.w; } } arr[MAXN];

int stck[MAXN], top;
ll f[MAXN], w[MAXN], l[MAXN];

int q[MAXN], _l, _r;

db X(int i) { return 1.0 * l[i + 1]; }
db Y(int i) { return 1.0 * f[i]; }
db slope(int i, int j) { return 1.0 * (Y(i) - Y(j)) / (X(i) - X(j)); }
db G(int i) { return -1.0 * w[i]; }

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) scanf("%lld %lld", &arr[i].w, &arr[i].l);
    sort(arr + 1, arr + n + 1);
    for (int i = 1; i <= n; ++i) {
        while (top && arr[stck[top]].l <= arr[i].l) top --;
        stck[++top] = i;
    }
    for (int i = 1; i <= top; ++i) w[i] = arr[stck[i]].w, l[i] = arr[stck[i]].l;
    _l = _r = 1;
    for (int i = 1; i <= top; ++i) {
        while (_l < _r && slope(q[_l], q[_l + 1]) >= G(i)) _l ++;
        int j = q[_l];
        f[i] = f[j] + w[i] * l[j + 1];
        while (_l < _r && slope(q[_r], q[_r - 1]) < slope(q[_r], i)) _r --;
        q[++ _r] = i;
    }
    printf("%lld\n", f[top]);
    return 0;
}

[APIO2010]特别行动队

横坐标单调递增，维护上凸包，斜率单调递减。

有 DP 转移式子：

f(i) = \max_{j = 1}^{i - 1} + a * (s(i) - s(j))^2 + b * (s(i) - s(j)) + c

其中，s(n) = \sum_{i = 1}^n x_i

写成斜率优化的样子：

f(j) - b * s(j) + a * s(j) ^ 2 = f(i) - a * s(i) ^ 2 - b * s(i) - c + 2 * a * s(i) * s(j)

要使纵截距最大，维护上凸包，题中 a < 0，故斜率单调递减，横坐标单调递增。

稍微有一点不一样，改一下大于小于号即可。

时间复杂度 O(n)。

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double db;

const int MAXN = 1e6 + 10;

int n;
ll s[MAXN], f[MAXN], a, b, c;

db X(int i) { return 1.0 * s[i]; }
db Y(int i) { return 1.0 * (f[i] - b * s[i] + a * s[i] * s[i]); }
db slope(int i, int j) { return (Y(i) - Y(j)) / (X(i) - X(j)); }
db G(int i) { return 2.0 * a * s[i]; }

int q[MAXN], l, r;

int main() {
    scanf("%d %lld %ld %lld", &n, &a, &b, &c);
    for (int i = 1; i <= n; ++i) scanf("%lld", &s[i]), s[i] += s[i - 1];
    l = r = 1; q[1] = 0;
    for (int i = 1; i <= n; ++i) {
        while (l < r && slope(q[l], q[l + 1]) > G(i)) l ++;
        int j = q[l];
        f[i] = f[j] + (s[i] - s[j]) * (s[i] - s[j]) * a + (s[i] - s[j]) * b + c;
        while (l < r && slope(i, q[r]) > slope(q[r], q[r - 1])) r --;
        q[++ r] = i;
    }
    printf("%lld\n", f[n]);
    return 0;
}

[IOI2002]任务安排

横坐标单调递增，维护下凸包，斜率单调递增。

有一个很妙的方程：

f(i) = \min_{j = 1}^{i - 1} f(j) + t(i) * (c(i) - c(j)) + S * (c(n) - c(j))

其中，t(n) \leftarrow \sum_{i = 1}^n t(i), c(n) \leftarrow \sum_{i = 1} ^ n c(i)。

这个方程妙在，将费用（开机费用）提前计算了，就不必要知道到底启动了几次。

写成斜率优化的样子：

f(j) = f(i) - t(i) *c(i) - S * c(n) + c(j) * (S + t(i))

维护下凸包，斜率单调递增，横坐标单调递增。

和例题一样的维护方法。

时间复杂度 O(n)。

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double db;

const int MAXN = 1e4 + 10;

int n;
ll s, t[MAXN], c[MAXN], f[MAXN];

db X(int i) { return 1. * c[i]; }
db Y(int i) { return 1. * f[i]; }
db slope(int i, int j) { return (Y(i) - Y(j)) / (X(i) - X(j)); }
db G(int i) { return 1. * (t[i] + s); }

int q[MAXN], l, r;

int main() {
    scanf("%d %lld", &n, &s);
    for (int i = 1; i <= n; ++i) {
        scanf("%lld %lld", &t[i], &c[i]);
        t[i] += t[i - 1], c[i] += c[i - 1];
    }
    l = r = 1;
    for (int i = 1; i <= n; ++i) {
        while (l < r && slope(q[l], q[l + 1]) < G(i)) l ++;
        int j = q[l];
        f[i] = f[j] + t[i] * (c[i] - c[j]) + s * (c[n] - c[j]);
        while (l < r && slope(q[r], q[r - 1]) > slope(q[r], i)) r --;
        q[++r] = i;
    }
    printf("%lld\n", f[n]);
    return 0;
}

[SDOI2016]征途

横坐标单调递增，维护下凸包，斜率单调递增。

比上面的题都不那么裸了。

令这 m 天分别走 x_i 长度的路，长度总和为 sum。

答案为：

\begin{aligned} m^2 \times (\dfrac{1}{m}\sum_{i = 1}^m (x_i - \overline{x}) ^2 ) &= m \times \sum_{i = 1}^m (x_i - \overline{x}) ^ 2 \\ &= m \times (\sum_{i = 1}^m x_i^2 + \sum_{i = 1}^m (\dfrac{sum}{m}) ^ 2 - 2 \times \sum_{i = 1}^m x_i \times \dfrac{sum}{m}) \\ &= m \times \sum_{i = 1}^m x_i^2 + sum^2 - 2 \times m \times sum \times \dfrac{sum}{m} \\ &= m \times \sum_{i = 1}^m x_i^2 - sum^2 \end{aligned}

则只需要求出最小的 \sum_{i = 1}^m x_i^2 即可。其意义为：最小的每段平方的和。

考虑 f(i, j) 表示在前 i 个地方休息 j 天的最小平方和。

令 s(n) = \sum_{i = 1}^n x_i

有：

f(i, j) = \min_{k = 1}^ {i - 1} f(k, j - 1) + (s(i) - s(k)) ^ 2

展开写成斜率优化的式子为；

f(k, j - 1) + s(j) ^ 2 = f(i, j) - s(i) ^ 2 + 2 \times s(i) \times s(j)

要使截距最小，维护下凸包，斜率单调递增，横坐标单调递增。

对于每一个 j，都做一遍斜率优化即可。

还可以使用一下滚动优化，把第二维优化。

时间复杂度 O(nm)。

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double db;

const int MAXN = 3e3 + 10;

int n;
ll m, s[MAXN], sum, f[MAXN], g[MAXN];

db X(int i) { return 1.* s[i]; }
db Y(int i) { return 1.* (g[i] + s[i] * s[i]); }
db slope(int i, int j) { return (Y(i) - Y(j)) / (X(i) - X(j)); }
db K(int i) { return 2.* s[i]; }

int main() {
    scanf("%d %lld", &n, &m);
    for (int i = 1; i <= n; ++i) scanf("%lld", &s[i]), sum += s[i], s[i] += s[i - 1];
    for (int i = 1; i <= n; ++i) f[i] = INT_MAX;
    for (int i = 1; i <= m; ++i) {
        memcpy(g, f, sizeof f), memset(f, 0, sizeof f);
        static int q[MAXN];
        int l = 0, r = 0;
        q[0] = q[1] = q[r] = 0;
        for (int j = 1; j <= n; ++j) {
            while (l < r && slope(q[l], q[l + 1]) < K(j)) l ++;
            int k = q[l];
            f[j] = g[k] + (s[j] - s[k]) * (s[j] - s[k]);
            while (l < r && slope(q[r], q[r - 1]) > slope(q[r], j)) r --;
            q[++ r] = j;
        }
    }
    printf("%lld\n", m * f[n] - sum * sum);
    return 0;
}

变种

斜率不单调

利用二分查找。

例题：[SDOI2012]任务安排

斜率不单调，则需维护整个凸包，每次转移的时候需要在单调队列（此时已经退化为单调栈）上二分。

具体而言，本题需要维护一个下凸包。则每次转移时二分找到第一个斜率大于 k(i) 的两个点，用靠左的那个点进行转移即可。

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

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double db;

const int MAXN = 3e5 + 10;

int n;
ll s, c[MAXN], t[MAXN], f[MAXN];

ll X(int i) { return c[i]; }
ll Y(int i) { return (f[i] - s * c[i]); }
//db slope(int i, int j) { return (Y(i) - Y(j)) / (X(i) - X(j)); }
ll K(int i) { return t[i]; }

ll deltaX(int i, int j) { return (X(i) - X(j)); }
ll deltaY(int i, int j) { return (Y(i) - Y(j)); }

int q[MAXN], l, r;

int find(ll g) {
    int L = l, R = r - 1, ret = -1;
    while (L <= R) {
        int mid = (L + R) >> 1;
        if (deltaY(q[mid + 1], q[mid]) < g * deltaX(q[mid + 1], q[mid])) L = mid + 1;
        else ret = mid, R = mid - 1;
    }
    if (ret == -1) return q[r];
    return q[ret];
}

int main() {
    scanf("%d %lld", &n, &s);
    for (int i = 1; i <= n; ++i) {
        ll tt, cc;
        scanf("%lld %lld", &tt, &cc);
        t[i] = t[i - 1] + tt, c[i] = c[i - 1] + cc;
    }
    l = r = 1, q[1] = 0;
    for (int i = 1; i <= n; ++i) {
        int j = find(K(i));
        f[i] = f[j] + t[i] * (c[i] - c[j]) + s * (c[n] - c[j]);
        while (l < r && deltaY(q[r], q[r - 1]) * deltaX(i, q[r]) >= deltaY(i, q[r]) * deltaX(q[r], q[r - 1])) r --;
        q[++ r] = i;
    }
    printf("%lld\n", f[n]);
    return 0;
}

OI-dp-优化-斜率优化 OI-数据结构-单调队列

codeforces 1354/edu. 87 题解与总结
上一篇 «
简单离散数学与二项式反演学习笔记
» 下一篇