P1478 陶陶摘苹果(升级版)

题目描述

又是一年秋季时,陶陶家的苹果树结了n个果子。陶陶又跑去摘苹果,这次她有一个a公分的椅子。当他手够不着时,他会站到椅子上再试试。

这次与NOIp2005普及组第一题不同的是:陶陶之前搬凳子,力气只剩下s了。当然,每次摘苹果时都要用一定的力气。陶陶想知道在s<0之前最多能摘到多少个苹果。

现在已知n个苹果到达地上的高度xi,椅子的高度a,陶陶手伸直的最大长度b,陶陶所剩的力气s,陶陶摘一个苹果需要的力气yi,求陶陶最多能摘到多少个苹果。

输入输出格式

输入格式:

第1行:两个数 苹果数n,力气s。

第2行:两个数 椅子的高度a,陶陶手伸直的最大长度b。

第3行~第3+n-1行:每行两个数 苹果高度xi,摘这个苹果需要的力气yi。

输出格式:

只有一个整数,表示陶陶最多能摘到的苹果数。

输入输出样例

输入样例#1:

8 15
20 130
120 3
150 2
110 7
180 1
50 8
200 0
140 3
120 2

输出样例#1:

4

说明

所有数据:n<=5000 a<=50 b<=200 s<=1000

      xi<=280  yi<=100

题目描述

又是一年秋季时,陶陶家的苹果树结了n个果子。陶陶又跑去摘苹果,这次她有一个a公分的椅子。当他手够不着时,他会站到椅子上再试试。

这次与NOIp2005普及组第一题不同的是:陶陶之前搬凳子,力气只剩下s了。当然,每次摘苹果时都要用一定的力气。陶陶想知道在s<0之前最多能摘到多少个苹果。

现在已知n个苹果到达地上的高度xi,椅子的高度a,陶陶手伸直的最大长度b,陶陶所剩的力气s,陶陶摘一个苹果需要的力气yi,求陶陶最多能摘到多少个苹果。

输入输出格式

输入格式:

第1行:两个数 苹果数n,力气s。

第2行:两个数 椅子的高度a,陶陶手伸直的最大长度b。

第3行~第3+n-1行:每行两个数 苹果高度xi,摘这个苹果需要的力气yi。

输出格式:

只有一个整数,表示陶陶最多能摘到的苹果数。

输入输出样例

输入样例#1:

8 15
20 130
120 3
150 2
110 7
180 1
50 8
200 0
140 3
120 2

输出样例#1:

4

说明

所有数据:n<=5000 a<=50 b<=200 s<=1000

      xi<=280  yi<=100

上面那位大哥想到了用dp求解,但是那个方程我确实没看懂,,,
其实这个题可以看做是dp的背包问题
我们有一个体力s
对于每一个能摘(高度在范围之内)苹果我们只有摘或者不摘两种可能性
so我们就把这个题转化到了01背包问题
状态转移方程
dp[i][j]=max(dp[i-1][j],dp[i-1][j-a[i].v]+1);
顺便说一下,为了保证dp的效率,我事先把所有的苹果都按高度排了个序,如果当前的苹果够不到,说明往后的苹果都够不到,直接退出就可以
于是乎就产生了一个问题,第dp[n][maxt]不一定是最大值
最大值需要在每次dp的时候都比较一下
这是这道题和01背包唯一不同的地方
 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<cmath>
 5 #include<algorithm>
 6 using namespace std;
 7 int n,maxt;
 8 int chair,hand;
 9 struct node
10 {
11     int high;
12     int v;
13 }a[10001];
14 int comp(const node & a,const node & b)
15 {
16     if(a.high!=b.high)
17     return a.high<b.high;
18     else 
19     return a.v<b.v;
20 }
21 int dp[5001][1001];
22 int ans=0;
23 int main()
24 {
25     scanf("%d%d%d%d",&n,&maxt,&chair,&hand);
26     hand=hand+chair;
27     for(int i=1;i<=n;i++)
28         scanf("%d%d",&a[i].high,&a[i].v);
29     sort(a+1,a+n+1,comp);
30     for(int i=1;i<=n;i++)
31     {
32         if(hand>=a[i].high)
33         {
34             for(int j=0;j<=maxt;j++)
35             {
36                 if(a[i].v<=j)
37                     dp[i][j]=max(dp[i-1][j],dp[i-1][j-a[i].v]+1);
38                 else
39                 dp[i][j]=dp[i-1][j];
40                 ans=max(ans,dp[i][j]);
41             }
42             
43         }
44         else
45         break;
46     }
47     printf("%d",ans);
48     return 0;
49 }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏数据小魔方

Leaflet在线地图进阶宝典——json素材操纵与图层面板控制

这篇教程憋了很久,其实算是3个月前leaflet在线地图系列的进阶篇,但是因为当时对于leaflet地图的数据源结构理解有限,技能勉强操控shp数据源,对于js...

5543
来自专栏云计算D1net

如何逼死一名程序员?

都说大家忍不了程序员,其实程序员也有受不了的事儿 ? 栈和队列的区别是啥? 吃多了拉就是队列;吃多了吐就是栈。 ? 世界上最遥远的距离不是生与死,而是你亲手制造...

36514
来自专栏Python小屋

报告PPT(123页):Python编程基础精要

本文所发PPT是董付国老师2018年5月份在成都第二届全国高校“数据科学与大数据技术”专业教学研讨会(电子工业出版社)上作报告用的。

3613
来自专栏java一日一条

59条令人捧腹但真实的程序员编程语录

我收集了很多关于软件开发者的编程语录。这些语录和软件开发维护、调试、软件bug、软件设计和文档、代码质量、测试和管理等相关。下面这59条编程语录虽然令人捧腹但也...

1494
来自专栏我分享我快乐

w3c官网解读——js基础教程_js语句和注释

帮0基础的你分析w3c官网的javascript基础教程及小案例,让喜欢javascript的朋友可以爱上他并能拥抱他!

922
来自专栏生信技能树

标准TCGA大文章需要哪些数据?[赠重磅资料]

很多人总是问我如何挖掘TCGA的数据,发文章! 可是他却连TCGA的数据是怎么来的都不知道,TCGA发了几十篇CNS大文章(自己测序的)了,每篇文章都有几百个左...

3425
来自专栏程序人生

如何提高代码质量?

好的程序员从来不靠格子衫或者颜值吃饭,就像你家 C 罗明明可以靠脸,却非要用不断精进的身体和技术迷倒你。

1230
来自专栏小樱的经验随笔

CTF---安全杂项入门第一题 丘比龙的最爱

丘比龙的最爱分值:10 来源: 2014HCTF 难度:易 参与人数:4498人 Get Flag:1366人 答题人数:1384人 解题通过率:99% 传说,...

3117
来自专栏企鹅号快讯

编程语言简史:有人不喜欢花括号,于是他发明了 Python

编程语言有上千种,但是流行的不过10来种,那些我们经常使用的编程语言都是谁在什么时候创造出来的呢?Casper Beyer为我们进行了整理。 ? 1800年 J...

2477
来自专栏数据结构与算法

BZOJ 3714: [PA2014]Kuglarz(最小生成树)

Description 魔术师的桌子上有n个杯子排成一行,编号为1,2,…,n,其中某些杯子底下藏有一个小球,如果你准确地猜出是哪些杯子,你就可以获得奖品。花...

3835

扫码关注云+社区

领取腾讯云代金券