【题目来源】
https://www.luogu.com.cn/problem/P1833
【题目描述】
爱与愁大神后院里种了 n 棵樱花树，每棵都有美学值 Ci(0<Ci≤200)。爱与愁大神在每天上学前都会来赏花。爱与愁大神可是生物学霸，他懂得如何欣赏樱花：一种樱花树看一遍过，一种樱花树最多看 Fi(0≤Fi≤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）。
【输出格式】
只有一个整数，表示最大美学值。
【输入样例】
6:50 7:00 3
2 1 0
3 3 1
4 5 4
【输出样例】
11
【数据范围】
100% 数据：Te-Ts≤1000（即开始时间距离结束时间不超过 1000 分钟），n≤10000。保证Te，Ts 为同一天内的时间。
样例解释：赏第一棵樱花树一次，赏第三棵樱花树 2 次。
【算法分析】
● 核心逻辑：将 0/1 背包（数量 cnt=1）与多重背包（数量 cnt≥1）统一归为一类，通过二进制拆分转化为 0/1 背包，采用逆序遍历处理；将完全背包（数量 cnt=0）单独处理，采用正序遍历。
【算法代码】
#include <bits/stdc++.h>
using namespace std;const int N=1e3+5;
int f[N];int get_time() {int h,m;scanf("%d:%d",&h,&m);return h*60+m;
}int main() {//1.读入时间+樱花数量int st=get_time();int ed=get_time();int V=ed-st;int n;cin>>n;//2.二进制拆分处理多重背包for(int i=1; i<=n; i++) {int vol,val,cnt;cin>>vol>>val>>cnt;if(cnt==0) { //完全背包：正序for(int j=vol; j<=V; j++) {f[j]=max(f[j],f[j-vol]+val);}} else { //多重背包：二进制拆分int k=1;while(k<=cnt) {int v=vol*k;int w=val*k;for(int j=V; j>=v; j--) {f[j]=max(f[j],f[j-v]+w);}cnt-=k;k<<=1;}if(cnt>0) {for(int j=V; j>=vol*cnt; j--) {f[j]=max(f[j],f[j-vol*cnt]+val*cnt);}}}}cout<<f[V]<<endl;return 0;
}/*
in:
6:50 7:00 3
2 1 0
3 3 1
4 5 4out:
11
*/
【参考文献】
https://blog.csdn.net/hnjzsyjyj/article/details/159526923
https://blog.csdn.net/hnjzsyjyj/article/details/126230183
https://blog.csdn.net/hnjzsyjyj/article/details/126190151
https://blog.csdn.net/hnjzsyjyj/article/details/126229598