樱花 - 题目列表

题意

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

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

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

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

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

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

思路

先看一个可以直接验证正确性的朴素解：

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

struct Item {
    int t;
    int c;
    int p;
};

static int parse_time(const string &s) {
    size_t pos = s.find(':');
    int h = stoi(s.substr(0, pos));
    int m = stoi(s.substr(pos + 1));
    return h * 60 + m;
}

static vector<Item> items;
static vector<vector<int>> memo;

static int dfs(int idx, int rest) {
    if (idx == (int)items.size()) {
        return 0;
    }

    int &res = memo[idx][rest];
    if (res != -1) {
        return res;
    }

    res = dfs(idx + 1, rest);

    const Item &it = items[idx];
    int limit = rest / it.t;
    if (it.p > 0) {
        limit = min(limit, it.p);
    }

    for (int take = 1; take <= limit; ++take) {
        res = max(res, dfs(idx + 1, rest - take * it.t) + take * it.c);
    }
    return res;
}

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

    string start_s, end_s;
    int n;
    if (!(cin >> start_s >> end_s >> n)) {
        return 0;
    }

    int limit = parse_time(end_s) - parse_time(start_s);
    if (limit < 0) {
        limit += 24 * 60;
    }

    items.resize(n);
    for (int i = 0; i < n; ++i) {
        cin >> items[i].t >> items[i].c >> items[i].p;
    }

    memo.assign(n, vector<int>(limit + 1, -1));
    cout << dfs(0, limit) << '\n';
    return 0;
}

brute.cpp 直接按“每棵树看几次”去枚举，思路很直观，但只适合小数据。

为了更容易观察转移过程，可以先看样例的 DP 表。

这张表展示了容量 0..10 在处理每棵树后的最优值变化：

处理到的物品	2	3	4	5	6	7	8	9	10
初始	0	0	0	0	0	0	0	0	0
`2 1 0`	1	1	2	2	3	3	4	4	5
`3 3 1`	1	3	3	4	4	5	5	6	6
`4 5 4`	1	3	5	5	6	8	10	10	11

从表里可以直接看到，最后 dp[10] = 11，也就是样例答案。而且这三个物品分别对应了完全背包、0/1 背包和多重背包三种情况。

关键观察是：题目本质上还是一维背包，只是物品类型混在一起了。

Pi = 0 时，是完全背包，容量正序更新
Pi > 0 时，是多重背包，先二进制拆分成若干个 0/1 物品，再容量倒序更新

这样就能把所有情况统一成标准背包转移。

DP 公式

设 $dp_t$ 表示总时间不超过 $t$ 时能获得的最大价值。若某棵树可以采 $cnt_i$ 次，耗时 $cost_i$ ，价值 $value_i$ ，则统一形式是：

dp_t=\max(dp_t,\ dp_{t-cost_i}+value_i)

当 $cnt_i=0$ 时表示完全背包， $t$ 正序枚举；当 $cnt_i>0$ 时先二进制拆分成若干个 0/1 物品，再让 $t$ 倒序枚举。最终答案为：

dp_T

公式解释：不同樱花树对应不同背包类型。无限次采摘用正序完全背包，有限次数先拆成若干个 0/1 物品再倒序更新，本质都在维护时间容量下的最大价值。

代码

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

static int parse_time(const string &s) {
    size_t pos = s.find(':');
    int h = stoi(s.substr(0, pos));
    int m = stoi(s.substr(pos + 1));
    return h * 60 + m;
}

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

    string start_s, end_s;
    int n;
    if (!(cin >> start_s >> end_s >> n)) {
        return 0;
    }

    int limit = parse_time(end_s) - parse_time(start_s);
    if (limit < 0) {
        limit += 24 * 60;
    }

    vector<int> dp(limit + 1, 0);

    for (int i = 0; i < n; ++i) {
        int t, c, p;
        cin >> t >> c >> p;

        if (t > limit) {
            continue;
        }

        if (p == 0) {
            // 无限次：完全背包，容量正序。
            for (int j = t; j <= limit; ++j) {
                dp[j] = max(dp[j], dp[j - t] + c);
            }
        } else {
            // 有上限：二进制拆分成若干个 0/1 物品。
            int k = 1;
            int rest = p;
            while (rest > 0) {
                int take = min(k, rest);
                int wt = take * t;
                int val = take * c;
                if (wt <= limit) {
                    for (int j = limit; j >= wt; --j) {
                        dp[j] = max(dp[j], dp[j - wt] + val);
                    }
                }
                rest -= take;
                k <<= 1;
            }
        }
    }

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

复杂度

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

总结

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

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

一图流解析

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

樱花

目录

题意

思路

DP 公式

代码

复杂度

总结

一图流解析