樱花 - 题目列表

题意

有 n 棵樱花树，每棵树看一次要花 Ti 分钟，得到 Ci 的美学值。

Pi 表示这棵树最多能看多少次：

Pi = 0：可以无限次观看
Pi > 0：最多观看 Pi 次

要在 Te - Ts 分钟内，选择若干棵树观看若干次，使总美学值最大。

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

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

思路

一句话本质：混合背包—— $P_i=0$ 走完全背包（正序）， $P_i>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
35import sys

data = sys.stdin.buffer.read().decode().split()
ts_h, ts_m = map(int, data[0].split(':'))
te_h, te_m = map(int, data[1].split(':'))
n = int(data[2])

T = (te_h * 60 + te_m) - (ts_h * 60 + ts_m)

trees = []
idx = 3
for _ in range(n):
    t = int(data[idx])
    c = int(data[idx + 1])
    p = int(data[idx + 2])
    idx += 3
    trees.append((t, c, p))

best = 0

def dfs(i, time_left, value):
    global best
    if i == n:
        best = max(best, value)
        return
    t, c, p = trees[i]
    if p == 0:
        max_k = time_left // t
    else:
        max_k = min(p, time_left // t)
    for k in range(max_k + 1):
        dfs(i + 1, time_left - k * t, value + k * c)

dfs(0, T, 0)
print(best)

brute.py 对每棵树枚举看 $0 \sim \max_k$ 次。 $n$ 最大 $10000$ ，每棵树可选次数不确定，组合数爆炸。

怎么看出是混合背包？

$P_i = 0$ ：可无限次看 → 完全背包物品
$P_i = 1$ ：最多看一次 → 0/1 背包物品
$P_i > 1$ ：最多看 $P_i$ 次 → 多重背包物品

三种类型混在一起，但容量（时间）只有一个维度 $T$ 。核心是把每种类型统一到同一个 $dp$ 框架里。

为什么完全背包要正序枚举容量？

正序意味着转移 $dp_j \leftarrow \max(dp_j, dp_{j-t} + c)$ 时， $dp_{j-t}$ 可能已经是用过这件物品的状态。这恰恰允许"同一件物品取多次"。倒序则强制每件物品只用一次。

为什么多重背包要倒序？

二进制拆分后，每组只选一次——是 0/1 物品。倒序保证每组最多取一次，恰好拼出 $0 \sim P_i$ 的所有取法。

为什么要做二进制拆分而不是逐件枚举？

如果每件物品都枚举 $0 \sim P_i$ 次，时间复杂度是 $O(T \cdot \sum P_i)$ 。当 $P_i$ 很大时会超时。二进制拆分把 $P_i$ 拆成 $\log P_i$ 个包，总物品数降到 $O(\sum \log P_i)$ 。

拆完之后怎么处理？

每包形成一个新的 0/1 物品（重量 $= use \cdot t_i$ ，价值 $= use \cdot c_i$ ），然后倒序做 0/1 背包。最终 $dp_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#include <bits/stdc++.h>
using namespace std;

const int MAXT = 1005;

int T, n;
// dp[j] 表示在 j 分钟内能获得的最大美学值。
int dp[MAXT];

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

    int h1, m1, h2, m2;
    char colon;
    cin >> h1 >> colon >> m1;
    cin >> h2 >> colon >> m2;
    cin >> n;

    T = (h2 * 60 + m2) - (h1 * 60 + m1);  // 总可用分钟数

    for (int i = 1; i <= n; i++) {
        int t, c, p;
        cin >> t >> c >> p;               // 花费时间 t，美学值 c，次数 p

        if (p == 0) {                      // 能看无限次 → 完全背包正序
            for (int j = t; j <= T; j++) {
                dp[j] = max(dp[j], dp[j - t] + c);
            }
        } else {                           // 有限次 → 二进制分组转为 0/1 背包倒序
            int k = 1;
            while (p > 0) {
                int use = min(k, p);
                int wt = use * t;
                int wc = use * c;
                for (int j = T; j >= wt; j--) {
                    dp[j] = max(dp[j], dp[j - wt] + wc);
                }
                p -= use;
                k <<= 1;
            }
        }
    }

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

复杂度

时间复杂度： $O(\text{limit} \cdot (n + \sum \log P_i))$
空间复杂度： $O(limit)$

总结

这题的关键不是赏花本身，而是把每棵树的“可选次数”翻译成背包类型。

Pi = 0 走完全背包，Pi > 0 走多重背包，最后统一到一维 dp 就行。

一图流解析

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

樱花

目录

题意

思路

代码

复杂度

总结

一图流解析