rqnoj PID95:多多看DVD(加强版)

题目描述

多多进幼儿园了，今天报名了。只有今晚可以好好放松一下了（以后上了学后会很忙）。她的叔叔决定给他买一些动画片DVD晚上看。可是爷爷规定他们只能在一定的时间段L看完。（因为叔叔还要搞NOIP不能太早陪多多看碟，而多多每天很早就困了所以只能在一定的时间段里看碟）。多多列出一张表要叔叔给她买N张DVD碟，大多都是多多爱看的动画片（福音战士，机器猫，火影忍者，樱桃小丸子……）。这N张碟编号为（，，……N）。多多给每张碟都打了分Mi（Mi>），打分越高的碟说明多多越爱看。每张碟有播放的时间Ti。多多想在今晚爷爷规定的时间里看的碟总分最高。（必须把要看的碟看完，也就是说一张碟不能只看一半）。显然叔叔在买碟是没必要把N张全买了，只要买要看的就OK了，这样节省资金啊。而且多多让叔叔惯的特别任性只要他看到有几张就一定会看完。

可是出现了一个奇怪的问题，买碟的地方只买给顾客M（M<N）张碟，不会多也不会少。这可让多多叔叔为难了。怎么可以在N张碟中只买M张而且在规定时间看完，而且使总价值最高呢？

聪明的你帮帮多多的叔叔吧。

数据范围 by RQ

对于100%的数据m<n<= l<=

输入格式

输入文件有三行

第一行：两个数空格隔开的正整数，N，M，L（分别表示叔叔给多多买的碟的数量，商店要买给叔叔的碟的数量，爷爷规定的看碟的时间段）。

第二行到第N行，每行两个数：T，M，给出多多列表中DVD碟的信息。

输出格式

单独输出一行，表示多多今晚看的碟的总分。

如果商店卖给叔叔的M张碟无法在爷爷规定的时间看完输出0；

样例输入 

样例输出

３

题目

真·题目

　　if 你是一个小纯洁，请看上面的那个题目。

　　else 多多是个很污的小萝莉，她搞NOIP的叔叔也好不到哪去，这位叔叔热衷于给侄女买DVD，然后不知道从哪冒出来的爷爷就看不下去了，规定多多每天只能看L时间。多多让叔叔买n张DVD，每张DVD都有时长Ti和分数（多多的喜爱程度）Mi,好心的商人为了多多的身体着想，只卖给叔叔m张。请你满足多多的欲望，让她看碟的分数最高。输入文件有三行，第一行：两个数空格隔开的正整数，N，M，L（分别表示叔叔给多多买的碟的数量，商店要买给叔叔的碟的数量，爷爷规定的看碟的时间段）。第二行到第N行，每行两个数：T，M，给出多多列表中DVD碟的信息。单独输出一行，表示多多今晚看的碟的总分。如果多多一张也看不了欲求不满输出0；

　　芒果君：先贴代码~

 #include<cstdio>

 #include<algorithm>

 #include<iostream>

 #define inf -20000000

 using namespace std;

 int n,m,l,t[],s[],f[][],i,j,k;

 int main()

 {

     cin>>n>>m>>l;

     for(i=;i<=n;++i) cin>>t[i]>>s[i];

     for(i=;i<=n;++i)

         for(j=;j<=m;++j)

             f[i][j]=inf;

     for(i=;i<=n;++i)

         for(j=m;j>=;--j)

             for(k=l;k>=t[i];--k)

                 if(f[j-][k-t[i]]||j==) f[j][k]=max(f[j][k],f[j-][k-t[i]]+s[i]);

     if(f[m][l]==inf) cout<<""<<endl;

     else cout<<f[m][l]<<endl;

     return ;

 }

　　对于刚学01背包的各位dalao来说，如果听完下节完全背包的课，很快就会对循环的顺序产生疑惑。为什么01背包是逆序？那么我们一定要从动态规划的原理出发——每个dp最后的结果都是由无数个子结果“继承”而来，如果写成正序循环，那么就很可能出现当前物品重复放的情况。同时要关注f数组的意义，有时它和最后的大结果是同步的，即“在一定空间内能获得的最大价值”。在本题当中，由于选取物品的数量有限，就要多加一维来处理，用f[j][k]表示放j个物品，在k空间内获得的最大价值。为了控制只放一个物品，我们把多出的那层循环设置成逆序，并写了一个判断“存在继承可能”的if语句，这道题就算结束了。

巴特西

rqnoj PID95:多多看DVD(加强版)

最新文章

热门文章