首页 > 代码库 > rqnoj 多多看DVD
rqnoj 多多看DVD
/*f[i][j]表示 前j个时间 看完 i个所得的最大价值*/#include<iostream>#include<cstdio>#include<cstring>#include<string>#include<cmath>#include<algorithm>#include<cstdlib>using namespace std;int n,m,l,f[110][1010],ans;int main(){ scanf("%d%d%d",&n,&m,&l); for(int k=1;k<=n;k++) { int a,b; scanf("%d%d",&a,&b); for(int i=n;i>=0;i--) for(int j=l-a;j>=0;j--) if(f[i][j]!=0||i==0) f[i+1][j+a]=max(f[i+1][j+a],f[i][j]+b); } for(int i=0;i<=l;i++) if(f[m][i]>ans) ans=f[m][i]; printf("%d\n",ans); return 0;}
题目描述
多多进幼儿园了,今天报名了。只有今晚可以好好放松一下了(以后上了学后会很忙)。她的叔叔决定给他买一些动画片DVD晚上看。可是爷爷规定他们只能在一定的时间段L看完。(因为叔叔还要搞NOIP不能太早陪多多看碟,而多多每天很早就困了所以只能在一定的时间段里看碟)。多多列出一张表要叔叔给她买N张DVD碟,大多都是多多爱看的动画片(福音战士,机器猫,火影忍者,樱桃小丸子……)。这N张碟编号为(1,2,3……N)。多多给每张碟都打了分Mi(Mi>0),打分越高的碟说明多多越爱看。每张碟有播放的时间Ti。多多想在今晚爷爷规定的时间里看的碟总分最高。(必须把要看的碟看完,也就是说一张碟不能只看一半)。显然叔叔在买碟是没必要把N张全买了,只要买要看的就OK了,这样节省资金啊。而且多多让叔叔惯的特别任性只要他看到有几张就一定会看完。
可是出现了一个奇怪的问题,买碟的地方只买给顾客M(M<N)张碟,不会多也不会少。这可让多多叔叔为难了。怎么可以在N张碟中只买M张而且在规定时间看完,而且使总价值最高呢?
聪明的你帮帮多多的叔叔吧。
数据范围 by RQ
对于100%的数据m<n<=100 l<=1000
输入格式
输入文件有三行
第一行:两个数空格隔开的正整数,N,M,L(分别表示叔叔给多多买的碟的数量,商店要买给叔叔的碟的数量,爷爷规定的看碟的时间段)。
第二行到第N行,每行两个数:T,M,给出多多列表中DVD碟的信息。
输出格式
单独输出一行,表示多多今晚看的碟的总分。
如果商店卖给叔叔的M张碟无法在爷爷规定的时间看完输出0;
rqnoj 多多看DVD
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。