P1478 陶陶摘苹果（升级版）
2018-06-17 22:34:42来源：未知 阅读 ()
题目描述
又是一年秋季时，陶陶家的苹果树结了n个果子。陶陶又跑去摘苹果，这次她有一个a公分的椅子。当他手够不着时，他会站到椅子上再试试。
这次与NOIp2005普及组第一题不同的是：陶陶之前搬凳子，力气只剩下s了。当然，每次摘苹果时都要用一定的力气。陶陶想知道在s<0之前最多能摘到多少个苹果。
现在已知n个苹果到达地上的高度xi，椅子的高度a，陶陶手伸直的最大长度b，陶陶所剩的力气s，陶陶摘一个苹果需要的力气yi，求陶陶最多能摘到多少个苹果。
输入输出格式
输入格式：第1行：两个数 苹果数n，力气s。
第2行：两个数 椅子的高度a，陶陶手伸直的最大长度b。
第3行~第3+n-1行：每行两个数 苹果高度xi，摘这个苹果需要的力气yi。
输出格式：只有一个整数，表示陶陶最多能摘到的苹果数。
输入输出样例
8 15 20 130 120 3 150 2 110 7 180 1 50 8 200 0 140 3 120 2
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。
输出格式：只有一个整数，表示陶陶最多能摘到的苹果数。
输入输出样例
8 15 20 130 120 3 150 2 110 7 180 1 50 8 200 0 140 3 120 2
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 }
标签：
版权申明：本站文章部分自网络，如有侵权，请联系：west999com@outlook.com
特别注意：本站所有转载文章言论不代表本站观点，本站所提供的摄影照片，插画，设计作品，如需使用，请与原作者联系，版权归原作者所有
- 【洛谷】P1478 陶陶摘苹果（升级版）-全AC题解 2019-10-25
- P1478 陶陶摘苹果（升级版） 2019-08-26
- 洛谷P1316 丢瓶盖 2018-06-17
IDC资讯： 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营： 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程： Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术： Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧： 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作： FrontPages Dreamweaver Javascript css photoshop fireworks Flash
