剑锋所指,心之所向。

对于状态转移方程含有变量与常量的乘积项,并满足某些性质的 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_ji 全部删掉,这对答案没有贡献。

具体而言,以 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 题解与总结
上一篇 «
简单离散数学与二项式反演学习笔记
» 下一篇