[SDOI2012] 任务安排

题意

给定一列任务，要把它们分成若干连续批次处理。

每批开始前要先花 s 的启动时间。

同一批中的所有任务会在同一时刻完成，而每个任务会产生：

完成时刻 * C_i

的费用。

目标是让总费用最小。

思路

先看最直接的暴力 DP：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40#include <bits/stdc++.h>
using namespace std;

const long long INF = (1LL << 62);
const int MAXN = 5005;

int n;
long long s;
long long t[MAXN], c[MAXN];
long long sum_t[MAXN], sum_c[MAXN];
long long dp[MAXN];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    // brute.cpp：小数据朴素 DP。
    // 直接枚举上一批的结束位置。
    cin >> n;
    cin >> s;
    for (int i = 1; i <= n; i++) {
        cin >> t[i] >> c[i];
        sum_t[i] = sum_t[i - 1] + t[i];
        sum_c[i] = sum_c[i - 1] + c[i];
    }

    dp[0] = 0;
    for (int i = 1; i <= n; i++) {
        dp[i] = INF;
        for (int j = 0; j < i; j++) {
            long long cost = dp[j]
                           + (sum_t[i] - sum_t[j]) * (sum_c[n] - sum_c[j])
                           + s * (sum_c[n] - sum_c[j]);
            dp[i] = min(dp[i], cost);
        }
    }

    cout << dp[n] << '\n';
    return 0;
}

设：

sum_t[i] 表示前 i 个任务处理时间之和
sum_c[i] 表示前 i 个任务费用系数之和

如果最后一批是 j+1..i，那么这一批的贡献可以整理成：

dp[i] = min(dp[j] + (sum_t[i]-sum_t[j])(sum_c[n]-sum_c[j]) + s(sum_c[n]-sum_c[j]))

继续整理：

dp[i] = (sum_t[i]+s)sum_c[n] + min(dp[j] - (sum_t[i]+s)sum_c[j] - sum_t[j](sum_c[n]-sum_c[j]))

对固定 j 而言，后面这一项是关于 sum_t[i] + s 的一次函数。

于是可以把每个决策点 j 看成一条线，再用单调队列维护下凸壳。

由于：

查询量 sum_t[i] + s 单调递增
斜率 sum_c[j] 单调递增

所以总复杂度可以降到 $O(n)$ 。

DP 转移方程

核心状态：

dp[i] 为前 i 个任务的最小费用

核心转移：

dp[i]=(sum_t[i]+s)sum_c[n]+min(dp[j]-(sum_t[i]+s)sum_c[j]-sum_t[j](sum_c[n]-sum_c[j]))

答案收束：

dp[n]

代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65#include <bits/stdc++.h>
using namespace std;

const int MAXN = 300005;

int n;
long long s;
long long t[MAXN], c[MAXN];
long long sum_t[MAXN], sum_c[MAXN];
long long dp[MAXN];
int q[MAXN];

long long X(int i) {
    return sum_c[i];
}

long long Y(int i) {
    return dp[i] - sum_t[i] * (sum_c[n] - sum_c[i]);
}

bool better_front(int a, int b, long long k) {
    return (__int128) (Y(b) - Y(a)) <= (__int128) k * (X(b) - X(a));
}

bool bad(int a, int b, int cidx) {
    return (__int128) (Y(b) - Y(a)) * (X(cidx) - X(b))
         >= (__int128) (Y(cidx) - Y(b)) * (X(b) - X(a));
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;
    cin >> s;
    for (int i = 1; i <= n; i++) {
        cin >> t[i] >> c[i];
        sum_t[i] = sum_t[i - 1] + t[i];
        sum_c[i] = sum_c[i - 1] + c[i];
    }

    int head = 1, tail = 1;
    q[1] = 0;
    dp[0] = 0;

    for (int i = 1; i <= n; i++) {
        long long k = sum_t[i] + s;
        while (head < tail && better_front(q[head], q[head + 1], k)) {
            head++;
        }

        int j = q[head];
        dp[i] = dp[j]
              + (sum_t[i] - sum_t[j]) * (sum_c[n] - sum_c[j])
              + s * (sum_c[n] - sum_c[j]);

        while (head < tail && bad(q[tail - 1], q[tail], i)) {
            tail--;
        }
        q[++tail] = i;
    }

    cout << dp[n] << '\n';
    return 0;
}

复杂度

时间复杂度 $O(n)$ ，空间复杂度 $O(n)$ 。

总结

这题和很多“任务安排”类题一样，真正的关键是把：

一批任务的整体贡献

写成前缀和形式，再把它整理成：

当前状态固定部分
历史决策点形成的直线部分

这样斜率优化就出来了。

一图流解析

这张图把本题的建模、关键转移、实现检查和训练方法压缩到一页，适合读完正文后复盘。