任务调度

形式化题目

有 $n$ 个互相独立的任务，机器有两个 CPU 和一个 GPU。每个任务可以选择四种资源方案：单 CPU、双 CPU、单 CPU 加 GPU、双 CPU 加 GPU，对应耗时分别为 $a_i,b_i,c_i,d_i$ 。一个任务一旦开始就独占所用硬件直到结束，求完成全部任务的最短时间。

思路

先看小数据暴力：枚举下一个任务、资源方案和最早开工时间。

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
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-07-31 16:21
 * update_at: 2026-08-17 22:52
 */
// brute.cpp：小数据暴力解，枚举每个任务的资源方案和执行顺序。
#include <bits/stdc++.h>
using namespace std;

const int INF = 0x3f3f3f3f;

int n;
int run_time[45][7];
int resource_mask[7] = {1, 2, 3, 5, 6, 7, 0};
map<unsigned long long, int> memo;

unsigned long long make_key(int done, int cpu1, int cpu2, int gpu) {
    unsigned long long key = (unsigned long long)done;
    key = key * 512 + cpu1;
    key = key * 512 + cpu2;
    key = key * 512 + gpu;
    return key;
}

int dfs(int done, int cpu1, int cpu2, int gpu) {
    if (cpu1 > cpu2) {
        swap(cpu1, cpu2);
    }

    unsigned long long key = make_key(done, cpu1, cpu2, gpu);
    map<unsigned long long, int>::iterator it = memo.find(key);
    if (it != memo.end()) {
        return it->second;
    }

    if (done == (1 << n) - 1) {
        return max(cpu2, gpu);
    }

    int answer = INF;
    for (int task = 0; task < n; task++) {
        if ((done & (1 << task)) != 0) {
            continue;
        }

        for (int mode = 0; mode < 6; mode++) {
            int mask = resource_mask[mode];
            int start = 0;
            if ((mask & 1) != 0) {
                start = max(start, cpu1);
            }
            if ((mask & 2) != 0) {
                start = max(start, cpu2);
            }
            if ((mask & 4) != 0) {
                start = max(start, gpu);
            }

            int next_cpu1 = cpu1;
            int next_cpu2 = cpu2;
            int next_gpu = gpu;
            if ((mask & 1) != 0) {
                next_cpu1 = start + run_time[task][mode];
            }
            if ((mask & 2) != 0) {
                next_cpu2 = start + run_time[task][mode];
            }
            if ((mask & 4) != 0) {
                next_gpu = start + run_time[task][mode];
            }

            answer = min(answer, dfs(done | (1 << task), next_cpu1, next_cpu2, next_gpu));
        }
    }

    memo[key] = answer;
    return answer;
}

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

    cin >> n;
    for (int i = 0; i < n; i++) {
        int a, b, c, d;
        cin >> a >> b >> c >> d;
        run_time[i][0] = a;
        run_time[i][1] = a;
        run_time[i][2] = b;
        run_time[i][3] = c;
        run_time[i][4] = c;
        run_time[i][5] = d;
    }

    cout << dfs(0, 0, 0, 0) << '\n';
    return 0;
}

暴力的状态会随着任务顺序和资源方案组合快速增长，不能处理 $n=40$ 。

把双 CPU 方案抽成串行代价

双 CPU 方案和双 CPU 加 GPU 方案都会同时占用两台 CPU，因此它们执行时不能与任何其他任务重叠。对同一个任务，二者只需保留较短的耗时 min(b_i,d_i)，把选中的这些任务的总耗时记为 serial。

剩余两种方案分别是：

单 CPU，耗时 $a_i$ ：放到 CPU1 或 CPU2；
单 CPU 加 GPU，耗时 $c_i$ ：放到某一台 CPU，并同时占用 GPU。

设当前两台 CPU 的累计负载为 i,j，GPU 的累计负载为 k。在这些累计负载下，双 CPU 方案消耗的总时间最小值记为 dp[i][j][k]。任务转移时，可以把它放入 serial，也可以增加某台 CPU 的负载；若选择 CPU 加 GPU 方案，还要同时增加 GPU 负载。

固定一种分配后，串行任务可以整体放在前面；其余任务的三类资源负载分别独立排成时间轴，所需时间是 max(i,j,k)。所以该状态对应的答案为：

serial + \max(i,j,k)

状态转移演示

由于两台 CPU 完全同构，只保留 i <= j 的状态。下面用一个小状态表展示任务的选择：S 表示串行耗时，三元组表示 (CPU1, CPU2, GPU) 负载。

已处理任务	选择	新状态	`S`
无	初始	`(0,0,0)`	0
任务 1，耗时 `a=2,c=3,q=4`	单 CPU 放 CPU1	`(2,0,0)` 排序为 `(0,2,0)`	0
任务 1，耗时 `a=2,c=3,q=4`	CPU+GPU 放 CPU1	`(3,0,3)` 排序为 `(0,3,3)`	0
任务 1，耗时 `a=2,c=3,q=4`	双 CPU 方案	`(0,0,0)`	4
再处理 `a=1,c=2,q=4`，从 `(0,2,0), S=0`	单 CPU 放较轻 CPU	`(1,2,0)`	0

表中的每一行都只从上一层状态转移一次；最终遍历所有状态，取 S + max(i,j,k) 的最小值。

代码

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
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-07-31 16:21
 * update_at: 2026-08-17 22:52
 */
#include <bits/stdc++.h>
using namespace std;

const int INF = 0x3f3f3f3f;

int n;
int a[45], c[45], serial_time[45];

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

    cin >> n;

    // 只用单 CPU 运行所有任务，贪心分到当前负载较小的 CPU，得到一个上界。
    int cpu1_load = 0;
    int cpu2_load = 0;
    for (int i = 1; i <= n; i++) {
        int b, d;
        cin >> a[i] >> b >> c[i] >> d;
        serial_time[i] = min(b, d);

        if (cpu1_load <= cpu2_load) {
            cpu1_load += a[i];
        } else {
            cpu2_load += a[i];
        }
    }

    int limit = max(cpu1_load, cpu2_load);
    int width = limit + 1;
    int layer_size = width * width * width;
    vector<int> dp(2 * layer_size, INF);

    dp[0] = 0;

    for (int task = 1; task <= n; task++) {
        int current_layer = task & 1;
        int previous_layer = current_layer ^ 1;
        int current_offset = current_layer * layer_size;
        int previous_offset = previous_layer * layer_size;

        for (int cpu1 = 0; cpu1 <= limit; cpu1++) {
            for (int cpu2 = cpu1; cpu2 <= limit; cpu2++) {
                int current_base = current_offset + (cpu1 * width + cpu2) * width;
                const int *previous_same = &dp[previous_offset + (cpu1 * width + cpu2) * width];

                int cpu1_after_a = -1;
                int cpu2_after_a = -1;
                int cpu1_after_c = -1;
                int cpu2_after_c = -1;

                if (cpu1 >= a[task]) {
                    cpu1_after_a = previous_offset + ((cpu1 - a[task]) * width + cpu2) * width;
                }
                if (cpu2 >= a[task]) {
                    int next_cpu1 = cpu1;
                    int next_cpu2 = cpu2 - a[task];
                    if (next_cpu1 > next_cpu2) {
                        swap(next_cpu1, next_cpu2);
                    }
                    cpu2_after_a = previous_offset + (next_cpu1 * width + next_cpu2) * width;
                }
                if (cpu1 >= c[task]) {
                    cpu1_after_c = previous_offset + ((cpu1 - c[task]) * width + cpu2) * width;
                }
                if (cpu2 >= c[task]) {
                    int next_cpu1 = cpu1;
                    int next_cpu2 = cpu2 - c[task];
                    if (next_cpu1 > next_cpu2) {
                        swap(next_cpu1, next_cpu2);
                    }
                    cpu2_after_c = previous_offset + (next_cpu1 * width + next_cpu2) * width;
                }

                int c_time = c[task];
                for (int gpu = 0; gpu <= limit; gpu++) {
                    int value = previous_same[gpu] + serial_time[task];

                    if (cpu1_after_a != -1) {
                        value = min(value, dp[cpu1_after_a + gpu]);
                    }
                    if (cpu2_after_a != -1) {
                        value = min(value, dp[cpu2_after_a + gpu]);
                    }
                    if (gpu >= c_time) {
                        if (cpu1_after_c != -1) {
                            value = min(value, dp[cpu1_after_c + gpu - c_time]);
                        }
                        if (cpu2_after_c != -1) {
                            value = min(value, dp[cpu2_after_c + gpu - c_time]);
                        }
                    }

                    // 当前状态已经不可能得到不超过上界的答案，直接丢弃。
                    if (value + max(cpu2, gpu) > limit) {
                        value = INF;
                    }
                    dp[current_base + gpu] = value;
                }
            }
        }
    }

    int answer = INF;
    int final_offset = (n & 1) * layer_size;
    for (int cpu1 = 0; cpu1 <= limit; cpu1++) {
        for (int cpu2 = cpu1; cpu2 <= limit; cpu2++) {
            int base = final_offset + (cpu1 * width + cpu2) * width;
            for (int gpu = 0; gpu <= limit; gpu++) {
                answer = min(answer, dp[base + gpu] + max(cpu2, gpu));
            }
        }
    }

    cout << answer << '\n';
    return 0;
}

复杂度

令 U 为“所有任务只用单 CPU，并贪心分到两台 CPU”得到的完成时间。由于 $a_i\leqslant 10$ 、 $n\leqslant 40$ ，有 $U\leqslant 205$ 。状态数利用 CPU 对称性为 $O(U^3)$ ，每个任务做常数次转移，因此时间复杂度为 $O(nU^3)$ ，空间复杂度为 $O(U^3)$ 。

总结

这道题的关键是识别“双 CPU 任务”的全局阻塞性质，把它们从并行调度中抽出来作为串行代价。剩余任务只需记录三种资源的累计负载，再用滚动数组和 CPU 对称性压缩 DP。

图示解析

下面的流程展示从四种运行方案到最终状态 DP 的转换：

text

1
2
3
4
5
6四种方案
  |- 单 CPU: 增加 CPU1 或 CPU2 负载 a
  |- 单 CPU + GPU: 增加某台 CPU 与 GPU 负载 c
  `- 双 CPU / 双 CPU + GPU: 增加串行代价 min(b, d)
       `- 状态 (CPU1, CPU2, GPU, serial)
             `- 取 serial + max(CPU1, CPU2, GPU) 的最小值

其中 CPU1 和 CPU2 可以交换，因此程序把两者排序后只保留一半状态。serial 不作为数组维度，而是存入每个负载状态的最小值。

目录

形式化题目

思路

把双 CPU 方案抽成串行代价

状态转移演示

代码

复杂度

总结

图示解析