樱花
题目背景
《爱与愁的故事第四弹·plant》第一章。
题目描述
爱与愁大神后院里种了 \(n\) 棵樱花树,每棵都有美学值 \(C_i(0 \le C_i \le 200)\)。爱与愁大神在每天上学前都会来赏花。爱与愁大神可是生物学霸,他懂得如何欣赏樱花:一种樱花树看一遍过,一种樱花树最多看 \(A_i(0 \le A_i \le 100)\) 遍,一种樱花树可以看无数遍。但是看每棵樱花树都有一定的时间 \(T_i(0 \le T_i \le 100)\)。爱与愁大神离去上学的时间只剩下一小会儿了。求解看哪几棵樱花树能使美学值最高且爱与愁大神能准时(或提早)去上学。
输入格式
共 \(n+1\)行:
第 \(1\) 行:现在时间 \(T_s\)(几时:几分),去上学的时间 \(T_e\)(几时:几分),爱与愁大神院子里有几棵樱花树 \(n\)。这里的 \(T_s\),\(T_e\) 格式为:hh:mm
,其中 \(0 \leq hh \leq 23\),\(0 \leq mm \leq 59\),且 \(hh,mm,n\) 均为正整数。
第 \(2\) 行到第 \(n+1\) 行,每行三个正整数:看完第 \(i\) 棵树的耗费时间 \(T_i\),第 \(i\) 棵树的美学值 \(C_i\),看第 \(i\) 棵树的次数 \(P_i\)(\(P_i=0\) 表示无数次,\(P_i\) 是其他数字表示最多可看的次数 \(P_i\))。
输出格式
只有一个整数,表示最大美学值。
样例 #1
样例输入 #1
6:50 7:00 3
2 1 0
3 3 1
4 5 4
样例输出 #1
11
提示
\(100\%\) 数据:\(T_e-T_s \leq 1000\)(即开始时间距离结束时间不超过 \(1000\) 分钟),\(n \leq 10000\)。保证 \(T_e,T_s\) 为同一天内的时间。
样例解释:赏第一棵樱花树一次,赏第三棵樱花树 \(2\) 次。
解析
显然的混合背包问题,对于观看次数无限制的用完全背包,对于有限制的则用多重背包。
代码
#include <bits/stdc++.h>
using namespace std;
int dp[1001], t[10001], c[10001], p[10001];
int n, T, t1, t2, t3, t4;
char s;
int main() {
cin >> t1 >> s >> t2 >> t3 >> s >> t4;
T = 60 * (t3 - t1) + t4 - t2;
cin >> n;
for (int i = 1; i <= n; i ++) scanf("%d %d %d", &t[i], &c[i], &p[i]);
for (int i = 1; i <= n; i ++) {
if (p[i] == 0)//完全背包
for (int j = t[i]; j <= T; j ++) dp[j] = max(dp[j], dp[j - t[i]] + c[i]);
else {//多重背包(二进制拆分)
for (int x = 1; x <= p[i]; p[i] -= x, x <<= 1){
for (int j = T; j >= x * t[i]; j --)
dp[j] = max(dp[j], dp[j - x * t[i]] + x * c[i]);
}
if (p[i]) for (int j = T; j >= p[i] * t[i]; j --)
dp[j] = max(dp[j], dp[j - p[i] * t[i]] + p[i] * c[i]);
}
}
cout << dp[T];
return 0;
}
注意这段代码中的p[i]-=x, x<<=1不能交换位置,不然就RE了(出现负数)。
for (int x = 1; x <= p[i]; p[i] -= x, x <<= 1)