首页 > 代码库 > codevs2503失恋28天......
codevs2503失恋28天......
503 失恋28天-缝补礼物
时间限制: 1 s
空间限制: 32000 KB
题目等级 : 黄金 Gold
题目描述 Description
话说上回他给女孩送了n件礼物,由于是廉价的所以全部都坏掉了,女孩很在意这些礼物,所以决定自己缝补,但是人生苦短啊,女孩时间有限,她总共有m分钟能去缝补礼物。由于损坏程度不一样所以缝补的时间p也是不一样的,每件礼物呢,都有一个女孩的喜爱程度为w,后面还有一个数字h为这种礼物的件数。女孩想让自己的喜爱程度的和最大,那么请聪明的你帮她算一算!(注意:礼物非常多,不一定都能缝补完,女孩也不用把所有时间都花费)
输入描述 Input Description
第1行2个整数 m,n
第2行到第n+1行 每行三个整数 p,w,h
输出描述 Output Description
一个整数s表示最大的喜爱程度
样例输入 Sample Input
8 2
2 100 4
4 100 2
样例输出 Sample Output
400
数据范围及提示 Data Size & Hint
m<=10000
n<=100
p,h,w<=6000
//多重背包板子using namespace std;#include<iostream>#include<cstdio>#include<cstring>#define maxv 10000+100#define maxn 100+10int v[maxn],c[maxn],opt[maxv],h[maxn];int V,n,cnt;int main(){ cin>>V>>n; for(int i=1;i<=n;i++) cin>>v[i]>>c[i]>>h[i]; memset(opt,0,sizeof(opt)); for(int i=1;i<=n;i++) { for(int j=V;j>=1;j--) { for(int k=1;k<=h[i];k++) { if(j-k*v[i]>=0) opt[j]=max(opt[j],opt[j-k*v[i]]+k*c[i]); } } } cout<<opt[V]<<endl; return 0;}
codevs2503失恋28天......
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。