usaco-3.4.4 “破锣摇滚”乐队

题目描述

从 $N$ 首按创作时间排列的歌曲中选出尽量多的歌，依次装入至多 $M$ 张 CD。每张 CD 总时长不超过 $T$ ，一首歌不能拆分。输入第一行为 $N, T, M$ ，第二行为 $N$ 个整数表示每首歌长度。

样例输入：

text

1
24 5 2
4 3 4 2

样例输出：

text

思路

顺序固定，只需记录当前已开 CD 数 $d$ 与最后一张 CD 已用分钟 $u$ 。对每首歌枚举三种选择：丢弃、接在最后一张 CD 末尾、另开一张新 CD，保留歌曲数更多的状态。数据范围 $N,M,T \le 20$ ，直接做 $dp[d][u]$ 即可。

参考代码

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#!/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 05:45
# update_at: 2026-10-01 05:45

import sys

NEG = -10**9  # 状态不存在时的哨兵：让 max 忽略不可达的转移


def place(
    cur: dict[tuple[int, int], int], length: int, T: int, M: int
) -> dict[tuple[int, int], int]:
    """把一首长度为 length 的歌接进所有状态：丢弃 / 塞进当前 CD / 另开一张 CD。"""
    nxt = dict(cur)  # 丢弃这首歌：状态原样保留
    for (discs, used), songs in cur.items():
        if discs >= 1 and used + length <= T:  # 当前 CD 剩余空位足够
            key = (discs, used + length)
            nxt[key] = max(nxt.get(key, NEG), songs + 1)
        if discs < M and length <= T:  # 单独占用一张新 CD
            key = (discs + 1, length)
            nxt[key] = max(nxt.get(key, NEG), songs + 1)
    return nxt


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n, T, M = next(data), next(data), next(data)
    lengths = [next(data) for _ in range(n)]  # 歌曲按创作时间顺序给出

    # 状态 (已开的 CD 数, 最后一张 CD 已用分钟) -> 已选歌曲数；discs = 0 表示还没开过 CD
    state: dict[tuple[int, int], int] = {(0, 0): 0}
    for length in lengths:
        state = place(state, length, T, M)
    print(max(state.values()))


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
63
64
65/**
 * 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:36
 * update_at: 2026-10-06 10:36
 */

#include <iostream>
#include <algorithm>
using namespace std;

typedef long long ll;

ll n, T, M;               // 歌曲数、CD 容量、CD 张数
ll a[25];                 // 每首歌的长度
ll dp[25][25];            // dp[d][u]：已开 d 张 CD、最后一张已用 u 分钟时最多可选歌曲数

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

    cin >> n >> T >> M;
    for (ll i = 1; i <= n; ++i) cin >> a[i];

    // 初始化：只有 (0,0) 可达，其余为负无穷
    for (ll d = 0; d <= M; ++d)
        for (ll u = 0; u <= T; ++u)
            dp[d][u] = -1e9;
    dp[0][0] = 0;

    for (ll k = 1; k <= n; ++k) {           // 按创作顺序处理每首歌
        ll old[25][25];
        for (ll d = 0; d <= M; ++d)
            for (ll u = 0; u <= T; ++u)
                old[d][u] = dp[d][u];

        for (ll d = 0; d <= M; ++d) {
            for (ll u = 0; u <= T; ++u) {
                if (old[d][u] < 0) continue; // 不可达状态跳过

                // 1) 丢弃这首歌
                dp[d][u] = max(dp[d][u], old[d][u]);

                // 2) 接在当前 CD 末尾（前提是已经开过 CD）
                if (d >= 1 && u + a[k] <= T) {
                    dp[d][u + a[k]] = max(dp[d][u + a[k]], old[d][u] + 1);
                }

                // 3) 另开一张新 CD
                if (d < M && a[k] <= T) {
                    dp[d + 1][a[k]] = max(dp[d + 1][a[k]], old[d][u] + 1);
                }
            }
        }
    }

    ll ans = 0;
    for (ll d = 0; d <= M; ++d)
        for (ll u = 0; u <= T; ++u)
            ans = max(ans, dp[d][u]);

    cout << ans << "\n";
    return 0;
}

usaco-3.4.4 “破锣摇滚”乐队

目录

题目描述

思路

参考代码