樱花 - 题目列表

形式化题目

有 $n$ 种物品, 第 $i$ 种物品每件耗时 $T_i$ , 价值为 $C_i$ , 最多选择 $P_i$ 件. 当 $P_i=0$ 时可无限选择. 给定总容量 $V=T_e-T_s$ , 求总耗时不超过 $V$ 的最大总价值.

暴力解法

思路

对每棵树枚举观看次数, 递归处理下一棵树. 当前树最多能看 $\lfloor V/T_i\rfloor$ 次; 若 $P_i>0$ , 上限还要取 $P_i$ 与它的较小值. 到叶子时检查完整选择的总耗时, 并用可行方案更新答案.

这个枚举覆盖每种合法选择, 适合做小数据基线. 但每棵树都可能产生多个分支, 最坏方案数会指数增长, 不能处理 $n=10000$ .

代码

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/**
 * 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-26 14:34
 * update_at: 2026-10-26 16:36
 */
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

// brute.cpp：小数据暴力解，逐棵树枚举观看次数，仅用于理解和对拍。
const int MAXN = 10005;

ll n, limit_time;
ll tree_time[MAXN], beauty[MAXN], count_limit[MAXN];
ll choose_count[MAXN]; // choose_count[i] 表示完整方案中第 i 棵树观看的次数
ll answer;

void check_plan() {
    ll total_time = 0;
    ll total_beauty = 0;
    for (int i = 1; i <= n; i++) {
        total_time += choose_count[i] * tree_time[i];
        total_beauty += choose_count[i] * beauty[i];
    }
    if (total_time <= limit_time) {
        answer = max(answer, total_beauty);
    }
}

void dfs_choose(ll dep) {
    if (dep == n + 1) {
        check_plan();
        return;
    }

    ll max_count = limit_time / tree_time[dep];
    if (count_limit[dep] > 0) {
        max_count = min(max_count, count_limit[dep]);
    }

    // 这一层枚举第 dep 棵树观看 0 到 max_count 次。
    for (int take = 0; take <= max_count; take++) {
        choose_count[dep] = take;
        dfs_choose(dep + 1);
    }
}

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

    ll start_hour, start_minute, end_hour, end_minute;
    char colon;
    cin >> start_hour >> colon >> start_minute;
    cin >> end_hour >> colon >> end_minute;
    cin >> n;

    limit_time = (end_hour * 60 + end_minute) - (start_hour * 60 + start_minute);
    for (int i = 1; i <= n; i++) {
        cin >> tree_time[i] >> beauty[i] >> count_limit[i];
    }

    dfs_choose(1);
    cout << answer << '\n';
    return 0;
}

复杂度

最坏为 $O(\prod_i (1+\min(P_i,\lfloor V/T_i\rfloor)))$ , 其中 $P_i=0$ 时按 $\lfloor V/T_i\rfloor$ 计. 只用于小数据.

瓶颈

直接枚举重复处理了大量不同树之间的组合. 但总时间容量最多只有 1000, 因此可以按容量合并这些方案, 用动态规划记录每个容量下的最优价值.

正解

思路

建模

每棵树可以看作一种物品. Ti 是重量, Ci 是价值, 可用时间是背包容量. Pi 决定物品可以使用多少次.

下表把原题对象映射为背包含义. 行表示题目中的信息, 右列表示对应模型参数.

原题对象	背包含义
一棵樱花树	一种物品
看一次的时间 `Ti`	重量
看一次的美学值 `Ci`	价值
`Pi = 0`	完全背包物品
`Pi > 0`	最多使用 `Pi` 次的多重背包物品

表中每棵树的次数选择彼此独立, 但共用同一个时间容量. 因此按物品逐个更新一维 DP, 不需要记录观看顺序.

令 dp[j] 表示处理过的树中, 总耗时不超过 $j$ 分钟时能获得的最大美学值. 初值均为 0, 因为可以不看任何树.

下面用一棵耗时 2 分钟、美学值 3 的树展示完全背包的状态更新. 表中列是可用容量, 单元格是当前 dp[j]; 第二行是在这棵树处理后的状态.

容量 `j`	0	1	2	3	4	5
处理前	0	0	0	0	0	0
`Pi=0` 后	0	0	3	3	6	6

容量正序时, 更新 dp[4] 会读取已经更新过的 dp[2]=3, 所以同一棵树可再选一次. 若容量倒序, dp[4] 读到的仍是本轮开始前的 dp[2], 同一物品最多使用一次. 因此完全背包必须正序.

无限次数: 完全背包正序

当 Pi=0 时, 对容量从 Ti 到 $V$ 正序更新:

dp[j]=\max(dp[j],dp[j-T_i]+C_i).

正序的理由是转移来源可能刚在本轮更新. 这使同一棵树能连续进入方案, 与无限次观看一致.

有限次数: 二进制拆分 + 0/1 背包倒序

当 Pi>0 时, 不能把每次观看分别暴力枚举. 将次数上限拆成大小约为 $1,2,4,...$ 的组. 每组 x 看作一个重量为 $xT_i$ 、价值为 $xC_i$ 的 0/1 物品.

例如上限 13 可拆成 1, 2, 4, 6. 前三组能表示 0 到 7 次; 加上最后的 6 次组后, 能表示 0 到 13 次. 一般地, 已有组总和为 $S$ , 下一组取 $b\leqslant S+1$ , 则不选它可表示 0..S, 选它可表示 b..b+S. 两段没有缺口. 所有组总和恰为 $P_i$ , 所以每个 0..P_i 的次数都能表示, 且不会超过上限.

每组只能选一次, 因此是 0/1 物品. 对每组从大到小枚举容量:

dp[j]=\max(dp[j],dp[j-xT_i]+xC_i).

倒序时来源容量尚未被当前组更新, 防止同一组在一轮中重复使用. 这就是多重背包必须倒序的原因.

代码

C++17 是正式主解. Python 版本使用相同的混合背包与二进制拆分算法, 复杂度同阶. 它在满规模输入按 Python 三倍时限测试通过.

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/**
 * 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-26 13:27
 * update_at: 2026-10-26 16:36
 */
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int MAXT = 1005;

ll n, limit_time;
ll dp[MAXT]; // dp[j] 表示总耗时不超过 j 分钟时的最大美学值

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

    ll start_hour, start_minute, end_hour, end_minute;
    char colon;
    cin >> start_hour >> colon >> start_minute;
    cin >> end_hour >> colon >> end_minute;
    cin >> n;

    limit_time = (end_hour * 60 + end_minute) - (start_hour * 60 + start_minute);

    for (int i = 1; i <= n; i++) {
        ll tree_time, beauty, count_limit;
        cin >> tree_time >> beauty >> count_limit;

        if (count_limit == 0) {
            // 完全背包正序：当前容量可读到本轮刚更新的状态，因此同一棵树可重复选择。
            for (int j = tree_time; j <= limit_time; j++) {
                dp[j] = max(dp[j], dp[j - tree_time] + beauty);
            }
            continue;
        }

        // 二进制分组把有限次数拆成若干个 0/1 物品，每组只能选一次。
        ll group_size = 1;
        while (count_limit > 0) {
            ll use_count = min(group_size, count_limit);
            ll group_time = use_count * tree_time;
            ll group_beauty = use_count * beauty;

            // 0/1 背包倒序：来源状态尚未被当前组更新，保证本组最多选一次。
            for (int j = limit_time; j >= group_time; j--) {
                dp[j] = max(dp[j], dp[j - group_time] + group_beauty);
            }

            count_limit -= use_count;
            group_size <<= 1;
        }
    }

    cout << dp[limit_time] << '\n';
    return 0;
}

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#!/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-26 13:30
# update_at: 2026-10-26 14:12

import sys
def parse_time(value: bytes) -> int:
    """把 hh:mm 时间转换为从 0:00 起算的分钟数。"""
    hour, minute = map(int, value.split(b":"))
    return hour * 60 + minute


def apply_bounded_item(dp: list[int], limit_time: int, tree_time: int, beauty: int, count_limit: int) -> list[int]:
    """二进制拆分有限次数物品，并逐组进行倒序 0/1 背包。"""
    group_size = 1
    while count_limit > 0:
        use_count = min(group_size, count_limit)
        group_time = use_count * tree_time
        group_beauty = use_count * beauty

        if group_time <= limit_time:
            old_dp = dp
            dp = old_dp[:group_time] + [
                candidate if candidate > old_dp[capacity] else old_dp[capacity]
                for capacity in range(group_time, limit_time + 1)
                for candidate in (old_dp[capacity - group_time] + group_beauty,)
            ]

        count_limit -= use_count
        group_size <<= 1

    return dp


def solve() -> None:
    data = iter(sys.stdin.buffer.read().split())
    start_time = parse_time(next(data))
    end_time = parse_time(next(data))
    n = int(next(data))
    limit_time = end_time - start_time
    dp = [0] * (limit_time + 1)

    for _ in range(n):
        tree_time = int(next(data))
        beauty = int(next(data))
        count_limit = int(next(data))

        if count_limit == 0:
            # 正序让当前树的新状态继续参与转移，实现无限次选择。
            for capacity in range(tree_time, limit_time + 1):
                candidate = dp[capacity - tree_time] + beauty
                if candidate > dp[capacity]:
                    dp[capacity] = candidate
        else:
            dp = apply_bounded_item(dp, limit_time, tree_time, beauty, count_limit)

    print(dp[limit_time])


if __name__ == "__main__":
    solve()

复杂度

令 $K=\sum_{P_i>0} O(\log(P_i+1))$ 为二进制拆分后的组数. 完全背包物品各扫描一次容量, 拆分组各扫描一次容量.

时间复杂度: $O(V(n+K))$ .
空间复杂度: $O(V)$ .

总结

本题的判断依据是每种树的可选次数. 无限次选择用完全背包正序更新; 有限次选择先二进制拆分, 再按 0/1 背包倒序更新. 拆分保证次数范围完整, 容量方向保证单组不会被错误重复使用.

樱花

目录

形式化题目

暴力解法

思路

代码

复杂度

瓶颈

正解

思路

建模

无限次数: 完全背包正序

有限次数: 二进制拆分 + 0/1 背包倒序

代码

复杂度

总结