洛谷 P1833：樱花 ← 混合背包（01 + 完全 + 多重）

【题目来源】https://www.luogu.com.cn/problem/P1833【题目描述】爱与愁大神后院里种了 n 棵樱花树每棵都有美学值 Ci(0Ci≤200)。爱与愁大神在每天上学前都会来赏花。爱与愁大神可是生物学霸他懂得如何欣赏樱花一种樱花树看一遍过一种樱花树最多看 Fi(0≤Fi≤100)遍一种樱花树可以看无数遍。但是看每棵樱花树都有一定的时间 Ti(0Ti≤100)。爱与愁大神离去上学的时间只剩下一小会儿了。求解看哪几棵樱花树能使美学值最高且爱与愁大神能准时或提早去上学。【输入格式】共 n1 行第 1 行现在时间 Ts几时几分去上学的时间 Te几时几分爱与愁大神院子里有几棵樱花树 n。这里的 TsTe 格式为hh:mm其中 0≤hh≤230≤mm≤59且 hhmmn 均为正整数。第 2 行到第 n1 行每行三个正整数看完第 i 棵树的耗费时间 Ti第 i 棵树的美学值 Ci看第 i 棵树的次数 PiPi0 表示无数次Pi 是其他数字表示最多可看的次数 Pi。​​​​​​​【输出格式】只有一个整数表示最大美学值。​​​​​​​【输入样例】6:50 7:00 32 1 03 3 14 5 4​​​​​​​【输出样例】11​​​​​​​【数据范围】100% 数据Te-Ts≤1000即开始时间距离结束时间不超过 1000 分钟n≤10000。保证TeTs 为同一天内的时间。样例解释赏第一棵樱花树一次赏第三棵樱花树 2 次。【算法分析】●核心逻辑将 0/1 背包数量 cnt1与多重背包数量 cnt≥1统一归为一类通过二进制拆分转化为 0/1 背包采用逆序遍历处理将完全背包数量 cnt0单独处理采用正序遍历​​​​​​​。【算法代码】#include bits/stdc.h using namespace std; const int N1e35; int f[N]; int get_time() { int h,m; scanf(%d:%d,h,m); return h*60m; } int main() { //1.读入时间樱花树数量 int stget_time(); int edget_time(); int Ved-st; int n; cinn; //2.二进制拆分处理多重背包 for(int i1; in; i) { int vol,val,cnt; cinvolvalcnt; if(cnt0) { //完全背包正序 for(int jvol; jV; j) { f[j]max(f[j],f[j-vol]val); } } else { //多重背包二进制拆分 int k1; while(kcnt) { int vvol*k; int wval*k; for(int jV; jv; j--) { f[j]max(f[j],f[j-v]w); } cnt-k; k1; } if(cnt0) { for(int jV; jvol*cnt; j--) { f[j]max(f[j],f[j-vol*cnt]val*cnt); } } } } coutf[V]endl; return 0; } /* in: 6:50 7:00 3 2 1 0 3 3 1 4 5 4 out: 11 */【参考文献】https://blog.csdn.net/hnjzsyjyj/article/details/159526923https://blog.csdn.net/hnjzsyjyj/article/details/126230183https://blog.csdn.net/hnjzsyjyj/article/details/126190151https://blog.csdn.net/hnjzsyjyj/article/details/126229598