题海拾贝：P1833 樱花

        Hello大家好！很高兴我们又见面啦！给生活添点passion，开始今天的编程之路！

我的博客：<但凡.

我的专栏：《编程之路》、《数据结构与算法之美》、《题海拾贝》、《C++修炼之路》

欢迎点赞，关注！

1、题目

 P1833 樱花 - 洛谷

2、题解 

#include<iostream>
#include<string>
using namespace std;
const int N = 1e5 + 10;
int f[N];
int T[N], c[N], p[N];
int main()
{int x = 0;char ch = 0;int y = 0;int x1 = 0;char ch1 = 0;int y1 = 0;cin >> x >> ch >> y;cin >> x1 >> ch1 >> y1;int t = x1 * 60 + y1 - (x * 60 + y);int n = 0;cin >> n;for (int i = 1;i <= n;i++){cin >> T[i] >> c[i] >> p[i];}for (int i = 1;i <= n;i++){//在前i个中挑选最大时间不超过j的最大价值if (p[i] == 0){//完全背包for (int j = T[i];j <= t;j++){f[j] = max(f[j], f[j - T[i]] + c[i]);}}else{//多重背包和01背包for (int j = t;j >= T[i];j--){for (int k = 1;k <= p[i]&&k*T[i]<=j;k++)//注意多重背包这里要限制两个{//注意空间优化后的多重背包k是从1开始的//虽然对于这个题来说没有区别，但是遇到别的题就不一定了f[j] = max(f[j], f[j - k * T[i]] + c[i]*k);}}}}cout << f[t] << endl;return 0;
}