题解报告——垃圾陷阱

题目网址：

https://www.luogu.org/problemnew/show/P1156

题目描述

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

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

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

假设卡门预先知道了每个垃圾扔下的时间t(0< t<=1000)，以及每个垃圾堆放的高度h(1<=h<=25)和吃进该垃圾能维持生命的时间f(1<=f<=30)，要求出卡门最早能逃出井外的时间，假设卡门当前体内有足够持续10小时的能量，如果卡门10小时内没有进食，卡门就将饿死。

看看如此可爱的小奶牛，等待你来拯救哦！！！

那我们来看看这道题的思路

1.首先对于每个掉下的垃圾来说我们都有两种选择：吃或不吃

所以我们可以定一个数组f[i][j]来表示在第 i 个物品掉落时，达到高度 j 所能活到的最大时间

1 struct sd{
2     int time,h,w;
3 }junk[105];
4 const int INF=99999999;
5 int f[105][105];
6 int len,n;

2.找状态转移方程

我们便可以得到两个状态转移方程（当然要判断在活着的前提下）

f[i][j]=max(f[i][j],f[i-1][j]+junk[i].w);--->不吃

f[i][j]=max(f[i][j],f[i-1][j-junk[i].h]);--->吃掉

 1 f[0][0]=10;
 2 for(int i=1;i<=n;i++)
 3 for(int j=0;j<=len;j++)
 4 {
 5      if(f[i-1][j]>=junk[i].time)
 6      f[i][j]=max(f[i][j],f[i-1][j]+junk[i].w);
 7         
 8       if(j>=junk[i].h)
 9       if(f[i-1][j-junk[i].h]>=junk[i].time)
10       f[i][j]=max(f[i][j],f[i-1][j-junk[i].h]);
11  }
12

3.查到结果

当我们的 j 达到指定高度时，且当前可存活到的时间点大于第 i 个物品掉落的时间，那这次物品掉落的时间 i 就是最短时间

1 if(j==len&&f[i][j]>=junk[i].time)
2         {
3             printf("%d",junk[i].time);
4             exit(0);
5         }

但如果查询完了都没找到最短时间，那么我们就在再循环一次，这一次我们一遇到垃圾就吃掉，因为知道不可能存活的，所以我们保证到死之前都一直吃。。。

1 int ans=10;
2     for(int i=1;i<=n;i++)
3     {
4         if(ans>=junk[i].time)
5         ans+=junk[i].w;
6         else break;
7     }
8     printf("%d",ans);

最后来看看代码吧。。。

 1 #include<cstdio>
 2 #include<algorithm>
 3 using namespace std;
 4 struct sd{
 5     int time,h,w;
 6 }junk[105];
 7 const int INF=99999999;
 8 int f[105][105];
 9 int len,n;
10 bool cmp(sd a,sd b)
11 {
12     return a.time<b.time;
13 }
14 void dp()
15 {
16     f[0][0]=10;
17     for(int i=1;i<=n;i++)
18     for(int j=0;j<=len;j++)
19     {
20         if(f[i-1][j]>=junk[i].time)
21         f[i][j]=max(f[i][j],f[i-1][j]+junk[i].w);
22         
23         if(j>=junk[i].h)
24         if(f[i-1][j-junk[i].h]>=junk[i].time)
25         f[i][j]=max(f[i][j],f[i-1][j-junk[i].h]);
26         
27         if(j==len&&f[i][j]>=junk[i].time)
28         {
29             printf("%d",junk[i].time);
30             exit(0);
31         }
32     }
33     int ans=10;
34     for(int i=1;i<=n;i++)
35     {
36         if(ans>=junk[i].time)
37         ans+=junk[i].w;
38         else break;
39     }
40     printf("%d",ans);
41 }
42 int main()
43 {
44     scanf("%d%d",&len,&n);
45     for(int i=1;i<=n;i++)
46     scanf("%d%d%d",&junk[i].time,&junk[i].w,&junk[i].h);
47     for(int i=1;i<=n;i++)
48     for(int j=0;j<=len;j++)
49     f[i][j]=-INF;
50     sort(junk+1,junk+1+n,cmp);
51     dp();
52     
53     return 0;
54 }