小书童——刷题大军

题意

总时间只有 r。必须先做一些作业，使总分至少达到 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#include <bits/stdc++.h>
using namespace std;

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

    int n, m, k, r;
    cin >> n >> m >> k >> r;

    vector<int> like(n), homework_time(m), homework_score(m);
    for (int i = 0; i < n; ++i) {
        cin >> like[i];
    }
    for (int i = 0; i < m; ++i) {
        cin >> homework_time[i];
    }
    for (int i = 0; i < m; ++i) {
        cin >> homework_score[i];
    }

    int best = 0;
    for (int mask = 0; mask < (1 << m); ++mask) {
        int used = 0;
        int score = 0;
        for (int i = 0; i < m; ++i) {
            if (mask & (1 << i)) {
                used += homework_time[i];
                score += homework_score[i];
            }
        }
        if (score < k || used > r) {
            continue;
        }

        int left_time = r - used;
        for (int sub = 0; sub < (1 << n); ++sub) {
            int cost = 0;
            int cnt = 0;
            for (int i = 0; i < n; ++i) {
                if (sub & (1 << i)) {
                    cost += like[i];
                    ++cnt;
                }
            }
            if (cost <= left_time) {
                best = max(best, cnt);
            }
        }
    }

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

下面是另一种「01 序列」风格的暴力写法。它先枚举每项作业选不选，再枚举每道喜欢题做不做；每一段选择都先生成完整 01 序列，再统一检查时间和分数限制：

另一种暴力写法：01 序列

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// brute_01_style.cpp：01 序列风格暴力，分别枚举作业选不选、喜欢题做不做。
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 15;
const int MAXM = 15;

int n, m, k, r;
int like_time[MAXN];
int homework_time[MAXM], homework_score[MAXM];
int choose_homework[MAXM]; // choose_homework[i] = 0/1，表示第 i 项作业不做/做
int choose_like[MAXN];     // choose_like[i] = 0/1，表示第 i 道喜欢题不做/做
int answer;
int homework_used_time;

int calc_homework_time() {
    int total = 0;
    for (int i = 1; i <= m; i++) {
        if (choose_homework[i] == 1) total += homework_time[i];
    }
    return total;
}

int calc_homework_score() {
    int total = 0;
    for (int i = 1; i <= m; i++) {
        if (choose_homework[i] == 1) total += homework_score[i];
    }
    return total;
}

int calc_like_time() {
    int total = 0;
    for (int i = 1; i <= n; i++) {
        if (choose_like[i] == 1) total += like_time[i];
    }
    return total;
}

int calc_like_count() {
    int total = 0;
    for (int i = 1; i <= n; i++) {
        if (choose_like[i] == 1) total++;
    }
    return total;
}

void dfs_like(int dep) {
    if (dep == n + 1) {
        if (homework_used_time + calc_like_time() <= r) {
            int value = calc_like_count();
            if (answer < value) answer = value;
        }
        return;
    }

    for (int i = 0; i <= 1; i++) {
        choose_like[dep] = i;
        dfs_like(dep + 1);
    }
}

void dfs_homework(int dep) {
    if (dep == m + 1) {
        homework_used_time = calc_homework_time();
        if (homework_used_time <= r && calc_homework_score() >= k) {
            dfs_like(1);
        }
        return;
    }

    for (int i = 0; i <= 1; i++) {
        choose_homework[dep] = i;
        dfs_homework(dep + 1);
    }
}

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

    cin >> n >> m >> k >> r;
    for (int i = 1; i <= n; i++) {
        cin >> like_time[i];
    }
    for (int i = 1; i <= m; i++) {
        cin >> homework_time[i];
    }
    for (int i = 1; i <= m; i++) {
        cin >> homework_score[i];
    }

    answer = 0;
    dfs_homework(1);

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

真正的关键是把问题拆开。

第一步只考虑作业。为了让最后能刷更多喜欢题，作业部分显然应该在“达到至少 k 分”的前提下尽量少花时间。

这就是一个标准 0/1 背包：

每项作业只能选或不选一次；
分数是状态；
耗时是我们要最小化的量。

定义 dp[s] 表示达到分数 s 所需的最少时间，并把所有超过 k 的分数都压到 k。

求出 dp[k] 后，剩余时间就固定成 r - dp[k]。接下来喜欢题每道题的收益都一样，都是“题目数 +1”，所以当然应该优先做耗时最短的题。

DP 公式

设 $dp_s$ 表示达到分数 $s$ 所需的最少时间，并把超过目标分数 $k$ 的状态截断到 $k$ 。初始化：

dp_0=0,\quad dp_s=+\infty\ (s>0)

处理一道分数为 $score_i$ 、耗时为 $time_i$ 的作业时：

dp_{\min(k,s+score_i)}=\min\left(dp_{\min(k,s+score_i)},\ dp_s+time_i\right)

若剩余时间为 $R-dp_k$ ，再尽量多做耗时最短的喜欢题。

把喜欢题耗时排序，从小到大能做多少就做多少即可。

公式解释：为了通过考试，只关心达到某个分数所需的最少时间。超过目标分数后没有额外意义，所以统一压到 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#include <bits/stdc++.h>
using namespace std;

const int INF = 1000000000;

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

    int n, m, k, r;
    cin >> n >> m >> k >> r;

    vector<int> like(n + 1), homework_time(m + 1), homework_score(m + 1);
    for (int i = 1; i <= n; ++i) {
        cin >> like[i];
    }
    for (int i = 1; i <= m; ++i) {
        cin >> homework_time[i];
    }
    for (int i = 1; i <= m; ++i) {
        cin >> homework_score[i];
    }

    vector<int> dp(k + 1, INF);
    dp[0] = 0;
    for (int i = 1; i <= m; ++i) {
        for (int score = k; score >= 0; --score) {
            if (dp[score] == INF) {
                continue;
            }
            int next_score = min(k, score + homework_score[i]);
            dp[next_score] = min(dp[next_score], dp[score] + homework_time[i]);
        }
    }

    int left_time = r - dp[k];
    sort(like.begin() + 1, like.end());

    int answer = 0;
    for (int i = 1; i <= n; ++i) {
        if (left_time >= like[i]) {
            left_time -= like[i];
            ++answer;
        }
    }

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

复杂度

时间复杂度 $O(m * k + n log n)$ ，空间复杂度 $O(k + n + m)$ 。

总结

这题的核心不是把所有选择混在一起暴力枚举，而是先把“及格最少时间”独立出来。背包求出最优作业方案后，后面的喜欢题只剩一个很干净的贪心。

一图流解析

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