题目链接:传送门
题目背景
《爱与愁的故事第四弹·plant》第一章。
题目描述
爱与愁大神后院里种了n棵樱花树,每棵都有美学值Ci。爱与愁大神在每天上学前都会来赏花。爱与愁大神可是生物学霸,他懂得如何欣赏樱花:一种樱花树看一遍过,一种樱花树最多看Ai遍,一种樱花树可以看无数遍。但是看每棵樱花树都有一定的时间Ti。爱与愁大神离去上学的时间只剩下一小会儿了。求解看哪几棵樱花树能使美学值最高且爱与愁大神能准时(或提早)去上学。
输入格式:
共n+1行:
第1行:三个数:现在时间Ts(几点:几分),去上学的时间Te(几点:几分),爱与愁大神院子里有几棵樱花树n。
第2行~第n+1行:每行三个数:看完第i棵树的耗费时间Ti,第i棵树的美学值Ci,看第i棵树的次数Pi(Pi=0表示无数次,Pi是其他数字表示最多可看的次数Pi)。
输出格式:
只有一个整数,表示最大美学值。
输入样例
6:50 7:00 3
2 1 0
3 3 1
4 5 4
输出样例
11
每种樱花能被看的次数不同,混合背包的板子
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <complex>
#include <algorithm>
#include <climits>
#include <queue>
#include <map>
#include <vector>
#include <iomanip>
#define
#define
#define
using namespace std;
int t1, t2, t3, t4, V, n, T[A], C[A], P[A], f[A];
int main() {
scanf("%d:%d", &t1, &t2);
scanf("%d:%d", &t3, &t4);
cin >> n;
V = (t3 - t1) * 60 - t2 + t4;
for (int i = 1; i <= n; i++) cin >> T[i] >> C[i] >> P[i];
for (int i = 1; i <= n; i++)
if (P[i] == 0) {
for (int j = T[i]; j <= V; j++)
f[j] = max(f[j], f[j - T[i]] + C[i]);
}
else {
for (int k = 1; k <= P[i]; k++)
for (int j = V; j >= T[i]; j--)
f[j] = max(f[j], f[j - T[i]] + C[i]);
}
cout << f[V];
}