PP4902 程程看樱花（基础）

解题思路

第一步，把时间算出来。 上学前的时间是 T_e-T_s，把"几时：几分"都化成分钟再相减，得到总分钟数 cap。例如 6:50 到 7:00 就是 10 分钟。

第二步，判断题目类型。 三种樱花：看一遍的、最多看 P_i 遍的、可以看无数遍的（P_i=0）。这是"混合背包"：无限次的用完全背包，有限次的用二进制拆分转成 0/1 背包。

第三步，无限次处理。 对 P_i=0 的樱花，用完全背包正序循环：dp[j]=max(dp[j], dp[j-t[i]]+c[i])。

第四步，有限次处理。 对 P_i>0 的樱花，把它拆成 1、2、4、8……份（二进制拆分），每份当作一个 0/1 物品，用倒序循环更新。因为看太多遍也放不进时间，先把次数限制在 cap/t[i] 以内。

边界情况。 如果樱花需要的时间超过总时间 cap，直接跳过。用样例验证：10 分钟里，看 2 次"4 时间 5 美学值"再加 1 次"2 时间 1 美学值"，得到 11。

参考代码

// P4902 程程看樱花 混合背包：有的樱花限次数，有的无限次
#include <iostream>
using namespace std;
long long dp[1005]; // dp[j] 用 j 分钟能得到的最大美学值
int t[10005], c[10005], q[10005]; // t 时间, c 美学值, q 次数
int n; // 樱花树棵数
int main() {
    int h1, m1, h2, m2, i, j;
    cin >> h1; cin.get();
    cin >> m1 >> h2; cin.get();
    cin >> m2 >> n;
    int cap = (h2 * 60 + m2) - (h1 * 60 + m1); // 上学前的分钟数
    if (cap < 0) cap = 0;
    for (i = 0; i < n; i++) cin >> t[i] >> c[i] >> q[i];
    for (i = 0; i < n; i++) {
        if (t[i] > cap) continue; // 时间超过总时长，看不了
        if (q[i] == 0) {
            // 无数遍：完全背包，正序循环
            for (j = t[i]; j <= cap; j++)
                if (dp[j - t[i]] + c[i] > dp[j]) dp[j] = dp[j - t[i]] + c[i];
        } else {
            // 最多 q[i] 遍：二进制拆分转 0/1 背包
            int s = q[i];
            if (s > cap / t[i]) s = cap / t[i]; // 最多只能看这么多遍
            int k = 1;
            while (s > 0) {
                int num = (k < s) ? k : s; // 本次拆出的棵数
                for (j = cap; j >= t[i] * num; j--)
                    if (dp[j - t[i] * num] + c[i] * num > dp[j])
                        dp[j] = dp[j - t[i] * num] + c[i] * num;
                s -= num;
                k <<= 1;
            }
        }
    }
    cout << dp[cap] << endl;
    return 0;
}

复杂度分析

时间复杂度是 O(n×cap)（n 为樱花棵数，cap 为总分钟数），二进制拆分后每个物品只多一个 log 因子。空间复杂度是 O(cap)。