文档章节

EOJ Monthly 2018.4 (E.小迷妹在哪儿(贪心&排序&背包)

o
 osc_z1hvg4cu
发布于 2018/04/24 21:15
字数 869
阅读 8
收藏 0

钉钉、微博极速扩容黑科技,点击观看阿里云弹性计算年度发布会!>>>

ultmaster 男神和小迷妹们玩起了捉迷藏的游戏。

小迷妹们都希望自己被 ultmaster 男神发现,因此她们都把自己位置告诉了 ultmaster 男神,因此 ultmaster 男神知道了自己去找每个小迷妹所要花的时间。

已知发现第 i 小迷妹得到的分数为 aitrtr 为游戏剩余时间)。ultmaster 想知道他最多能拿多少分。

Input

第一行两个整数 n,T (1n105,1T300) 分别表示小迷妹数量,游戏总时间。

接下去 n 行,每行两个整数 ai,ti (1ai100,1ti300) 分别表示发现小迷妹的分数以及 ultmaster 男神发现小迷妹所需时间。

Output

一个整数,表示 ultmaster 在游戏中最多拿多少分。

Examples

input
2 10
2 5
1 6
output
10
input
3 5
5 4
1 1
10 6
output
5

Note

样例一:找到小迷妹一,找到后得分 2×(105)=10 分。
样例二:找到小迷妹一,找到后得分 5×(54)=5 分,之后再找到小迷妹二得分也是 0,所以最高得分 5 分。

(ps:比赛的时候发现这题,像发现了宝藏,不就是简单的背包嘛,然而一直没过,GG;虽然最后还是排名前三,但完全靠运气,因为这次数据出了一些问题,导致很多排序在我前面的都FST到我后面了。我的D题重测后也WA了。)
 
题解说要排序,为什么这里的背包前背包要排序呢:
 
--------------------------------------------分界线---------------------------------------------
 
背包是特殊的DP。 01问题的本质是该物品价值确定,然后决定选还是不选;而EOJ的寻找小迷妹的问题,是因为物品的价值并不明确,我们首先采用了排序的方法,保证了一种使每个物品都能获得的最优的顺序,当然使两个物品之间,这应该是保证了动态规划的最优子结构问题,然后对于这个背包我们又去决定每一个物品放还是不放......就是说我们先搞出一个顺序,使得背包容量能装下所有物品时能获得最大的价值,然后又因为背包空间有限,按照这个顺序来选择这个物品,能比后其他顺序选择这个物品获得价值更大......对于普通背包来说,是因为价值确定了,所以不用排序......

最优子结构解释一下:这里的价值和时间顺序有关,所以我们排序,那么让价值高的先占据背包。然后剩下的空余背包再去DP。

(总之,如果遇到价值和时间无关的,无需多想。有关的,注意一下是否需要排序)。

至于验证,就根据不同的题划不等式就行了。。。

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
int dp[310],ans;
struct in { int a,t; }s[100010];
bool cmp(in w,in v){ return w.a*v.t>v.a*w.t;}
int main()
{
    int N,T; 
    scanf("%d%d",&N,&T);
    for(int i=1;i<=N;i++)
        scanf("%d%d",&s[i].a,&s[i].t);
    sort(s+1,s+N+1,cmp);
    for(int i=1;i<=N;i++){
        for(int j=T-s[i].t;j>=0;j--) dp[j+s[i].t]=max(dp[j+s[i].t],dp[j]+(T-j-s[i].t)*s[i].a);
        for(int j=1;j<=T;j++) dp[j]=max(dp[j],dp[j-1]);
    }    
    cout<<dp[T]<<endl;
    return 0;
}

 

o
粉丝 0
博文 500
码字总数 0
作品 0
私信 提问
加载中
请先登录后再评论。

暂无文章

SO_REUSEADDR和SO_REUSEPORT有何不同? - How do SO_REUSEADDR and SO_REUSEPORT differ?

问题: The man pages and programmer documentations for the socket options SO_REUSEADDR and SO_REUSEPORT are different for different operating systems and often highly confusing.......

法国红酒甜
今天
28
0
asp.net core之SignalR

SignalR 是什么? ASP.NET Core SignalR 是一个开源的实时框架,它简化了向应用中添加实时 Web 功能的过程。 实时 Web 功能是服务器端能够即时的将数据推送到客户端,而无需让服务器等待客户端...

一介草民Coder
今天
24
0
如何通过日期属性对数组进行排序 - How to sort an array by a date property

问题: Say I have an array of a few objects: 说我有一些对象的数组: var array = [{id: 1, date: Mar 12 2012 10:00:00 AM}, {id: 2, date: Mar 8 2012 08:00:00 AM}]; How can I sort......

javail
今天
22
0
技术教程| 百度鹰眼历史轨迹查询:轨迹抽稀功能

本文作者:用****9 本篇教程中,我们将详细地说明鹰眼历史轨迹查询(gettrack接口)中,如何通过vacuate_grade选项对轨迹进行抽稀,以及不同的抽稀力度对轨迹产生的影响。 上一篇教程中,我们...

百度开发者中心
前天
24
0
Quartz的Misfire处理规则 错过任务执行时间的处理机制

调度(scheduleJob)或恢复调度(resumeTrigger,resumeJob)后不同的misfire对应的处理规则 CronTrigger withMisfireHandlingInstructionDoNothing ——不触发立即执行 ——等待下次Cron触发频率...

独钓渔
今天
7
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部