首页 > 代码库 > rqnoj PID95:多多看DVD(加强版)
rqnoj PID95:多多看DVD(加强版)
题目描述 多多进幼儿园了,今天报名了。只有今晚可以好好放松一下了(以后上了学后会很忙)。她的叔叔决定给他买一些动画片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; 样例输入 3 2 10 11 100 1 2 9 1 样例输出 3
真·题目
if 你是一个小纯洁,请看上面的那个题目。
else 多多是个很污的小萝莉,她搞NOIP的叔叔也好不到哪去,这位叔叔热衷于给侄女买DVD,然后不知道从哪冒出来的爷爷就看不下去了,规定多多每天只能看L时间。多多让叔叔买n张DVD,每张DVD都有时长Ti和分数(多多的喜爱程度)Mi,好心的商人为了多多的身体着想,只卖给叔叔m张。请你满足多多的欲望,让她看碟的分数最高。输入文件有三行,第一行:两个数空格隔开的正整数,N,M,L(分别表示叔叔给多多买的碟的数量,商店要买给叔叔的碟的数量,爷爷规定的看碟的时间段)。第二行到第N行,每行两个数:T,M,给出多多列表中DVD碟的信息。单独输出一行,表示多多今晚看的碟的总分。如果多多一张也看不了欲求不满输出0;
芒果君:先贴代码~
1 #include<cstdio> 2 #include<algorithm> 3 #include<iostream> 4 #define inf -20000000 5 using namespace std; 6 int n,m,l,t[1010],s[1010],f[1010][1010],i,j,k; 7 int main() 8 { 9 cin>>n>>m>>l; 10 for(i=1;i<=n;++i) cin>>t[i]>>s[i]; 11 for(i=1;i<=n;++i) 12 for(j=0;j<=m;++j) 13 f[i][j]=inf; 14 for(i=1;i<=n;++i) 15 for(j=m;j>=1;--j) 16 for(k=l;k>=t[i];--k) 17 if(f[j-1][k-t[i]]||j==1) f[j][k]=max(f[j][k],f[j-1][k-t[i]]+s[i]); 18 if(f[m][l]==inf) cout<<"0"<<endl; 19 else cout<<f[m][l]<<endl; 20 return 0; 21 }
对于刚学01背包的各位dalao来说,如果听完下节完全背包的课,很快就会对循环的顺序产生疑惑。为什么01背包是逆序?那么我们一定要从动态规划的原理出发——每个dp最后的结果都是由无数个子结果“继承”而来,如果写成正序循环,那么就很可能出现当前物品重复放的情况。同时要关注f数组的意义,有时它和最后的大结果是同步的,即“在一定空间内能获得的最大价值”。在本题当中,由于选取物品的数量有限,就要多加一维来处理,用f[j][k]表示放j个物品,在k空间内获得的最大价值。为了控制只放一个物品,我们把多出的那层循环设置成逆序,并写了一个判断“存在继承可能”的if语句,这道题就算结束了。
rqnoj PID95:多多看DVD(加强版)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。