洛谷 1156 垃圾陷阱

上题

题目意思很明确，接下来就是考虑这题怎么做了

明显的一道dp题目

而且有很明显的背包的元素，则我们可以考虑dp方程

dp[i]表示在i高度所拥有的生命值

从h~0开始循环

如果这个高度的生命值不小于这个垃圾丢下来的时间

如果高度+这个垃圾的高度>=d，就输出这个垃圾丢下来的时间

不然当前高度+当前垃圾的高度的生命值=max(h~0的生命值)，即不吃垃圾用它来堆，此时高度+=这个垃圾的高度

这个高度的生命值+=吃这个垃圾增长的生命值，即吃垃圾，此时高度不变

最后输出高度为0的生命值，即出不去存活的最长时间

看看代码应该就好理解了

 1 #include <cstdio>
 2 #include <cstdlib>
 3 #include <iostream>
 4 #include <algorithm>
 5 #include <cstring>
 6 #include <cmath>
 7 using namespace std;
 8 struct node
 9 {
10     int t,f,h;
11 }d[200];
12 int dp[200],n,h;
13 bool cmp(node a,node b)
14 {
15     return a.t<b.t;
16 }
17 int main()
18 {
19     scanf("%d %d",&h,&n);
20     for(int i=1;i<=n;i++)
21     {
22         scanf("%d %d %d",&d[i].t,&d[i].f,&d[i].h);
23     }
24     sort(d+1,d+n+1,cmp);
25     memset(dp,0,sizeof(dp));
26     dp[0]=10;
27     for(int i=1;i<=n;i++)
28     {
29         for(int j=h;j>=0;j--)
30         {
31             if(dp[j]-d[i].t>=0)
32             {
33                 if(j+d[i].h>=h)
34                 {
35                     printf("%d
",d[i].t);
36                     return 0;
37                 }
38                 dp[j+d[i].h]=max(dp[j+d[i].h],dp[j]);
39                 dp[j]+=d[i].f;
40             }
41         }
42     }
43     printf("%d
",dp[0]);
44     return 0;
45 }