当前位置：首页 > news >正文

P1833 樱花

news 来源：原创 2025/6/27 23:02:50

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≤h≤23，0≤m≤59，且h,m,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	11

说明/提示

100%数据：Te−Ts≤1000（即开始时间距离结束时间不超过1000分钟），n≤10000。保证Ts,Te为同一天内的时间。
样例解释：赏第一棵樱花树1次，赏第三棵樱花树2次。

思路：
同一天的时间计算和多重背包，01背包，完全背包。

代码：

#include <bits/stdc++.h>
using namespace std;const int N = 1e4 + 10;
const int MAX_TIME = 1005; 
struct Node {int t, c, p; 
} tree[N];string s1, s2;
int n, M;
int dp[N][MAX_TIME]; // 前i棵树，耗时j的最大美学值int fun(string s1, string s2) {size_t pos1 = s1.find(':');int h1 = stoi(s1.substr(0, pos1));int m1 = stoi(s1.substr(pos1 + 1)); // 提取分钟（冒号后）size_t pos2 = s2.find(':');int h2 = stoi(s2.substr(0, pos2));int m2 = stoi(s2.substr(pos2 + 1));return (h2 - h1) * 60 + (m2 - m1); // 题目保证同一天，无需处理负数
}int main() {cin >> s1 >> s2 >> n;M = fun(s1, s2); // 获取总时间for (int i = 1; i <= n; i++) {cin >> tree[i].t >> tree[i].c >> tree[i].p;}for (int i = 1; i <= n; i++) {int t = tree[i].t;int c = tree[i].c;int p = tree[i].p;for (int j = 0; j <= M; j++) {dp[i][j] = dp[i-1][j]; // 不选当前树if (p == 0)// 完全背包 { if (j >= t){dp[i][j] = max(dp[i][j], dp[i][j - t] + c); // 基于当前行，允许重复选}}else// 01背包（p=1）或多重背包（p>1） { int max_k = min(p, j / t); // 最多选min(p, j/t)次for (int k = 1; k <= max_k; k++) { if (j >= k * t) {dp[i][j] = max(dp[i][j], dp[i-1][j - k*t] + k*c); }}}}}int max_c = 0;for (int j = 0; j <= M; j++) {max_c = max(max_c, dp[n][j]);}cout << max_c << endl;return 0;
}