closefrom

一维数组f[high]=life

循环d~0

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

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

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

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

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

//My AC Code：

#include <cstdio>
#include <algorithm>
using namespace std;
int d,g,dp[105];
struct node{
    int t,f,h;
}gg[105];
bool cp(node a,node b){return a.t<b.t;}
int max(int a,int b){return a>b?a:b;}
int main(){
    scanf("%d%d",&d,&g);
    for(int i=1;i<=g;i++)scanf("%d%d%d",&gg[i].t,&gg[i].f,&gg[i].h);
    sort(gg+1,gg+g+1,cp);
    dp[0]=10;//高度为0时，依照题目规定，最多生存10小时
    for(int i=1;i<=g;i++)
        for(int j=d;j>=0;j--)
            if(dp[j]>=gg[i].t){//如果当前高度的生存时间大于等于这个垃圾扔下来的时间
                if(j+gg[i].h>=d){//当前高度，（在生存状态下），若用来搭建高度，大于等于d也就是这个垃圾堆的高度，也就是可以逃出垃圾堆，就直接输出当前的垃圾扔下去的时间
                    printf("%d",gg[i].t);
                    return 0;
                }
                dp[j+gg[i].h]=max(dp[j+gg[i].h],dp[j]);
                /*
                当前垃圾用来搭建垃圾堆，也就是不吃垃圾来维持生命，
                最多能生存多久，到底用来搭建生存的久还是用来吃生存的久（用来吃生存，搭建高度不变）
                */
                dp[j]+=gg[i].f;
                //当前高度，生存状态下，吃垃圾来维持生命
            }
            printf("%d",dp[0]);
    return 0;
}