usaco-3.1.2 总分

题目描述

给定竞赛限时 $M$ 与 $N$ 个题目种类，第 $i$ 个种类每道题耗时 $t_i$ 、得分 $p_i$ ，可以选任意多道。求总耗时不超过 $M$ 时的最大得分。

输入格式：第一行 $M,N$ ；接下来 $N$ 行每行两个整数，先得分后耗时。输出一行最大得分。

样例： $M=300,N=4$ ，种类为 $(100,60),(250,120),(120,100),(35,20)$ ，输出 $605$ 。

思路

令 $dp[t]$ 表示限时 $t$ 内的最大得分。外层枚举种类，内层容量从小到大扫描（正序），则 $dp[t-t_i]$ 已含本轮结果，同一种类可被反复选取，即完全背包。按耗时升序处理，若 $dp[t_i] \ge p_i$ 则该种类被支配，跳过。

参考代码

Python 版：

python

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#!/usr/bin/env python3
# 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-10-01 04:45
# update_at: 2026-10-01 04:45

import sys


def best_total(limit: int, types: list[tuple[int, int]]) -> int:
    """在限时 limit 内，从这些 (耗时, 得分) 种类里任选题目，最多能拿多少分。"""
    # dp[t] = 限时 t 内的最大得分。容量维正序遍历，dp[t - w] 已含本轮结果，
    # 同一种类因此能被反复选取；若每种至多选一题，这里必须改成倒序。
    dp = [0] * (limit + 1)
    for minutes, points in types:  # types 已按耗时升序
        if minutes > limit:
            break  # 耗时升序，后面的种类耗时更长，连一题都放不下
        if dp[minutes] >= points:
            # 前面（耗时不超过 minutes）的种类已经能用不超过 minutes 的时间拿到不少于 points
            # 的分：把最优解里每道这种题目都换成那一份，耗时不增、得分不降，所以这种类
            # 不会出现在任何最优解里，直接剪掉；同耗时的种类也因此只留下得分最高的那个。
            continue
        for t in range(minutes, limit + 1):
            candidate = dp[t - minutes] + points  # 至少再选一道这种题目
            if candidate > dp[t]:
                dp[t] = candidate
    return dp[limit]


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    limit, count = next(data), next(data)  # 竞赛限时 M 与题目"种类"数 N
    tokens = [next(data) for _ in range(2 * count)]  # 每个种类两个数：得分在前、耗时在后
    # 重排成 (耗时, 得分) 并按耗时升序；耗时相同时得分高的排前面，低分的会被剪掉。
    types = sorted(zip(tokens[1::2], tokens[0::2]), key=lambda kind: (kind[0], -kind[1]))

    print(best_total(limit, types))


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

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/**
 * 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-10-06 10:09
 * update_at: 2026-10-06 10:09
 */
#include <iostream>
#include <algorithm>
using namespace std;

typedef long long ll;

const int MAXM = 10000;

int M, N;
ll dp[MAXM + 1]; // dp[t] 表示限时 t 内的最大得分

struct Kind {
    int t; // 耗时
    int p; // 得分
} kinds[MAXM + 1];

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

    cin >> M >> N;
    for (int i = 1; i <= N; ++i) {
        int points, minutes;
        cin >> points >> minutes;
        kinds[i].t = minutes;
        kinds[i].p = points;
    }

    // 按耗时升序排序，耗时相同则得分高的在前
    for (int i = 1; i <= N; ++i) {
        for (int j = i + 1; j <= N; ++j) {
            if (kinds[j].t < kinds[i].t ||
                (kinds[j].t == kinds[i].t && kinds[j].p > kinds[i].p)) {
                Kind tmp = kinds[i];
                kinds[i] = kinds[j];
                kinds[j] = tmp;
            }
        }
    }

    for (int i = 1; i <= N; ++i) {
        int t = kinds[i].t;
        int p = kinds[i].p;
        if (t > M) break; // 耗时升序，后面的种类耗时更长，连一题都放不下
        if (dp[t] >= p) continue; // 被支配种类，跳过
        // 完全背包：容量正序遍历，同一种类可重复选取
        for (int cap = t; cap <= M; ++cap) {
            ll cand = dp[cap - t] + p;
            if (cand > dp[cap]) dp[cap] = cand;
        }
    }

    cout << dp[M] << "\n";
    return 0;
}

目录

题目描述

思路

参考代码