DP_垃圾陷阱

DP_垃圾陷阱_题解

Misser-X 2018-07-19 原文

垃圾陷阱（题目链接）

题目描述

卡门――农夫约翰极其珍视的一条Holsteins奶牛――已经落了到“垃圾井”中。“垃圾井”是农夫们扔垃圾的地方，它的深度为

卡门想把垃圾堆起来，等到堆得与井同样高时，她就能逃出井外了。另外，卡门可以通过吃一些垃圾来维持自己的生命。

每个垃圾都可以用来吃或堆放，并且堆放垃圾不用花费卡门的时间。

假设卡门预先知道了每个垃圾扔下的时间

输入输出格式

输入格式：

第一行为

第二到第

输出格式：

如果卡门可以爬出陷阱，输出一个整表示最早什么时候可以爬出；否则输出卡门最长可以存活多长时间。

输入输出样例

输入样例#1：

输出样例#1：

说明

[样例说明]

卡门堆放她收到的第一个垃圾：

卡门吃掉她收到的第

卡门堆放第

题目很水！多思考！
划重点：
#1：堆放垃圾以及吃垃圾不耗费时间
#2：根据题目得知没一波垃圾只有两种处理方法：吃掉、堆起来，因此使用一维dp就能AC，dp[i]表示高度为i时最高生命值为dp[i]
#3：虽然说堆得越高出井的越快，但也不应该先考虑堆起来，因为这样不能保证不饿死，所以应求在同一高度中最高生命值
#4：要将数据按时间排序
#5：不要忽略时间，时间决定人的生死与出井的时间

代码：

 1 #include<stdio.h>
 2 #include<algorithm>
 3 #define max(a,b) a>b?a:b
 4 using namespace std;
 5 /*
 6 初始值生命值， 
 7 即dp[0]为10， 
 8 dp[i]表示当高度为i时最大的生命值 
 9 */ 
10 int d,g,dp[110]={10};
11 struct data{int t,f,h;}s[110];
12 bool cmp(data a,data b)
13 {
14     return a.t<b.t;
15 }
16 int main()
17 {
18     scanf("%d%d",&d,&g);
19     for(int i=1;i<=g;++i)
20         scanf("%d%d%d",&s[i].t,&s[i].f,&s[i].h);
21     //按时间排序（STL美滋滋） 
22     sort(s+1,s+1+g,cmp);
23     //枚举掉落的垃圾 
24     for(int i=1;i<=g;++i)
25     {
26         //枚举高度 
27         for(int j=d;j>=0;--j)
28         {
29             if(dp[j]>=s[i].t)
30             {
31                 //如果当前高度＋当前垃圾的高度 ≥井的高度则直接输出当前时间
32                 if(j+s[i].h>=d)
33                 {
34                     printf("%d",s[i].t);
35                     return 0;
36                 }
37                 //使高度为j+s[i].h时的生命值最大
38                 dp[j+s[i].h]=max(dp[j],dp[j+s[i].h]);
39                 //吃垃圾，即更新dp[j]的最大生命值
40                 dp[j]+=s[i].f;
41             }
42         }
43     }
44     //如果没有出去输出他活了多长时间 
45     printf("%d",dp[0]);
46 }