[USACO3.1] 总分 Score Inflation

题意

有若干种题目，每种题目都有：

完成一道题所需的时间
完成一道题得到的分数

每种题目可以选很多道，要求在总时间不超过 T 的前提下，让总分最大。

这张表把题目翻译成了背包模型：

原题对象	背包含义
一种题目	一个可以重复使用的物品
完成时间	物品重量
获得分数	物品价值
总时间 `T`	背包容量

从这里可以看出，本题是标准的完全背包最大值模型。

思路

先看最直接的暴力：

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#include <bits/stdc++.h>
using namespace std;

// brute.cpp：小数据暴力解，把每种题目选多少道看成计数选择序列。

const int MAXN = 10005;

int t, n;
int cost[MAXN];
int points[MAXN];
int choose_count[MAXN]; // choose_count[i] 表示第 i 种题目选多少道
int answer;

bool check() {
    int used_time = 0;
    for (int i = 1; i <= n; i++) {
        used_time += choose_count[i] * cost[i];
    }
    return used_time <= t;
}

int calc_answer() {
    int total_score = 0;
    for (int i = 1; i <= n; i++) {
        total_score += choose_count[i] * points[i];
    }
    return total_score;
}

void dfs_choose(int dep) {
    if (dep == n + 1) {
        if (check()) {
            int value = calc_answer();
            if (answer < value) answer = value;
        }
        return;
    }

    // 第 dep 种题目可以选 0..t/cost[dep] 道。
    int limit = t / cost[dep];
    for (int cnt = 0; cnt <= limit; cnt++) {
        choose_count[dep] = cnt;
        dfs_choose(dep + 1);
    }
}

void read_input() {
    cin >> t >> n;
    for (int i = 1; i <= n; i++) {
        cin >> points[i] >> cost[i];
    }
}

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

    read_input();
    dfs_choose(1);
    cout << answer << '\n';

    return 0;
}

brute.cpp 把每种题目选多少道看成一层选择：choose_count[i] 表示第 i 种题目选择数量。递归先生成完整计数序列，叶子节点再检查总时间是否超限。

这个做法显然正确，但复杂度很高，只适合小数据验证。

关键观察是：每种题目都可以重复选，所以状态转移要允许同一种物品在本轮继续使用。

于是设：

dp[j] 表示时间不超过 j 时能获得的最大全分

这张表说明状态定义：

状态	含义
`dp[j]`	时间不超过 `j` 时能获得的最大全分

处理第 i 种题目 (points[i], cost[i]) 时：

不选它：dp[j] 保持原值
选它：从 dp[j - cost[i]] 转移过来，再加上 points[i]

因为同一种题目可以重复选，所以容量必须正序枚举：

dp[j] = max(dp[j], dp[j - cost[i]] + points[i])

最后输出 dp[T] 即可。

DP 公式

设 $dp_j$ 表示时间不超过 $j$ 时能获得的最大全分。对于分值 $points_i$ 、耗时 $cost_i$ 的题型：

dp_j=\max(dp_j,\ dp_{j-cost_i}+points_i)

同一种题型可以重复选，所以容量正序枚举。最终答案为：

dp_T

公式解释：题型可以重复做，所以是完全背包最大值。若本次再做一道耗时 cost_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#include <bits/stdc++.h>
using namespace std;

const int MAXT = 10005;
const int MAXN = 10005;

int t, n;
int points[MAXN];
int cost[MAXN];
int dp[MAXT]; // dp[j] 表示时间不超过 j 时能获得的最大全分

void read_input() {
    cin >> t >> n;
    for (int i = 1; i <= n; i++) {
        cin >> points[i] >> cost[i];
    }
}

void solve() {
    for (int i = 1; i <= n; i++) {
        // 每种题目可以选很多道，所以容量必须正序枚举。
        for (int j = cost[i]; j <= t; j++) {
            dp[j] = max(dp[j], dp[j - cost[i]] + points[i]);
        }
    }

    cout << dp[t] << '\n';
}

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

    read_input();
    solve();

    return 0;
}

复杂度

时间复杂度： $O(NT)$
空间复杂度： $O(T)$

总结

这题就是完全背包的标准模板题：

每种题目可以重复选
容量正序枚举
目标是最大化总分

以后看到“同一种选择可以重复做、总时间有限、总收益尽量大”这类条件时，就可以直接往完全背包上想。

一图流解析

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