目录

P1833 樱花 

思路

        时间转换处理

        动态规划

代码

---

P1833 樱花

题目背景

《爱与愁的故事第四弹·plant》第一章。

题目描述

爱与愁大神后院里种了 n 棵樱花树，每棵都有美学值 Ci(0 < Ci<=200)。爱与愁大神在每天上学前都会来赏花。爱与愁大神可是生物学霸，他懂得如何欣赏樱花：一种樱花树看一遍过，一种樱花树最多看 Pi(0 <= Pi <= 100)$ 遍，一种樱花树可以看无数遍。但是看每棵樱花树都有一定的时间 Ti(0 < Ti <=100)。爱与愁大神离去上学的时间只剩下一小会儿了。求解看哪几棵樱花树能使美学值最高且爱与愁大神能准时（或提早）去上学。

输入格式

共n+1行：

第 1 行：现在时间Ts（几时：几分），去上学的时间 Te（几时：几分），爱与愁大神院子里有几棵樱花树n。这里的Ts，Te 格式为：`hh:mm`，其中 0 <= hh<= 23，0 <= mm<= 59，且 hh,mm,n 均为正整数。

第 2 行到第 n+1 行，每行三个正整数：看完第 i 棵树的耗费时间 Ti，第 i 棵树的美学值 Ci，看第 i 棵树的次数 Pi（Pi = 0 表示无数次，Pi 是其他数字表示最多可看的次数 Pi）。

输出格式

只有一个整数，表示最大美学值。

输入输出样例 #1

输入 #1

6:50 7:00 3
2 1 0
3 3 1
4 5 4

输出 #1

11

说明/提示

对于100% 数据：Te-Ts <= 1000（即开始时间距离结束时间不超过1000 分钟），n <= 10000。保证 Te,Ts 为同一天内的时间。

样例解释：赏第一棵樱花树一次，赏第三棵樱花树 2 次。

思路

问题分析

题目是一个混合背包问题，包含三种物品：只能选一次的樱花树（01背包）、最多选Pi次的樱花树（多重背包）、可以选无限次的樱花树（完全背包）。需要将时间转换为分钟差作为背包容量，通过二进制拆分处理多重背包物品，最后使用动态规划求解最大美学值。

做法

时间转换处理

先把时间转为题目中运算所要求的时间(简单的公式操作)

将输入的时间格式hh:mm转换为分钟差：

• 计算开始时间Ts和结束时间Te的总分钟数
• 时间差W = (Te_hh * 60 + Te_mm) - (Ts_hh * 60 + Ts_mm)

在运算操作时在遇到Pi=0时用最大值，使整个DP过程成为一个完全背包问题，最后用背包DP的解法即可，压缩时间可用二分拆分和快速读入函数

动态规划

使用一维数组dp进行状态转移：

• dp[j]表示剩余时间为j分钟时的最大美学值
• 状态转移方程：dp[j] = max(dp[j], dp[j - a[i]] + b[i])，其中a[i]为时间消耗，b[i]为美学值

代码

#include <bits/stdc++.h>
using namespace std;

int n, W; // 樱花树数量和时间差（背包容量）
int t, c, p; // 当前樱花树的时间、美学值、次数限制
int a[100005]; // 拆分后的时间消耗数组
int b[100005]; // 拆分后的美学值数组
int cur; // 当前拆分后的物品数量
int dp[1005]; // DP数组，dp[j]表示剩余时间j时的最大美学值

// 快速读入函数（适用于大数据量）
inline int read() {
    int x = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9') {
        if (ch == '-') f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        x = x * 10 + ch - '0';
        ch = getchar();
    }
    return x * f;
}

int main() {
    // 处理时间输入（格式为hh:mm）
    int a1, a2, b1, b2;
    char cc; // 用于读取冒号
    cin >> a1 >> cc >> a2 >> b1 >> cc >> b2;
    // 计算时间差（转换为分钟）
    W = 60 * (b1 - a1) + (b2 - a2);
    
    // 读取樱花树数量
    n = read();
    
    // 处理每棵樱花树
    while (n--) {
        t = read(); // 时间消耗
        c = read(); // 美学值
        p = read(); // 次数限制
        
        // 完全背包处理（Pi=0表示无限次）
        if (p == 0) {
            p = W / t; // 最多可选次数
        }
        
        // 多重背包二进制拆分
        int base = 1;
        while (p >= base) {
            cur++;
            b[cur] = base * c; // 拆分后的美学值
            a[cur] = base * t; // 拆分后的时间消耗
            p -= base;
            base <<= 1; // 二进制增长
        }
        // 处理剩余次数
        if (p > 0) {
            cur++;
            a[cur] = p * t;
            b[cur] = p * c;
        }
    }
    
    // 01背包动态规划
    for (int i = 1; i <= cur; i++) {
        for (int j = W; j >= a[i]; j--) {
            dp[j] = max(dp[j], dp[j - a[i]] + b[i]);
        }
    }
    
    // 输出结果
    cout << dp[W];
    return 0;
}
 

这就是整篇题的题解

谢谢大家