洛谷p1833-樱花

题目链接：P1833 樱花 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

题干：

爱与愁大神后院里种了 nn 棵樱花树，每棵都有美学值 C_i(0 \le C_i \le 200)Ci(0≤Ci≤200)。爱与愁大神在每天上学前都会来赏花。爱与愁大神可是生物学霸，他懂得如何欣赏樱花：一种樱花树看一遍过，一种樱花树最多看 A_i(0 \le A_i \le 100)Ai(0≤Ai≤100) 遍，一种樱花树可以看无数遍。但是看每棵樱花树都有一定的时间 T_i(0 \le T_i \le 100)Ti(0≤Ti≤100)。爱与愁大神离去上学的时间只剩下一小会儿了。求解看哪几棵樱花树能使美学值最高且爱与愁大神能准时（或提早）去上学。

Input

共 n+1n+1行：

第 11 行：现在时间 T_sTs（几时：几分），去上学的时间 T_eTe（几时：几分），爱与愁大神院子里有几棵樱花树 nn。这里的 T_sTs，T_eTe 格式为：hh:mm，其中 0 \leq hh \leq 230≤hh≤23，0 \leq mm \leq 590≤mm≤59，且 hh,mm,nhh,mm,n 均为正整数。

第 22 行到第 n+1n+1 行，每行三个正整数：看完第 ii 棵树的耗费时间 T_iTi，第 ii 棵树的美学值 C_iCi，看第 ii 棵树的次数 P_iPi（P_i=0Pi=0 表示无数次，P_iPi 是其他数字表示最多可看的次数 P_iPi）。

Output

只有一个整数，表示最大美学值。

思路：

本蒟蒻是没想出来TAT，看了其他dalao的思路。

大体思路是把各种用二进制拆分，然后就是01背包了。

讲下二进制拆分：

对于存在多个的，都可以用二进制来表示，例如：7可以拆成1、2、4，如果有剩余（不够凑够二进制下一位）的就直接放在下一位就行了。由二进制的数字，我们可以组合到从1到这个数字的所有可能性，所以是一种快捷的遍历方式，例如数字7可以用拆分到1、2、4，由这些二进制数字我们可以组合成1到7的所有可能重量，实现一种较为方便的遍历方式。

代码：

void init(){for(int i=1;i<=n;i++){int count=1; //计算当前拆分到哪个2的倍数while(c[i]){  //直到拆分完结束w[++now]=count*a[i];  //当前这份的重量*单个的重量v[now]=count*b[i];c[i]-=count;  //用完的要减去count*=2; if(c[i]

#include 
#include 
#include 
using namespace std;
const int N=1e7+5;
const int M=1e5+5;
int num,w[N],v[N];
int a[M],b[M],c[M],f[N];
int time1,n;
int now=0;
void init(){for(int i=1;i<=n;i++){int count=1;while(c[i]){w[++now]=count*a[i];v[now]=count*b[i];c[i]-=count;count*=2;if(c[i]=w[i];j--){f[j]=max(f[j],f[j-w[i]]+v[i]);}}cout<

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！