题解 P1156 【垃圾陷阱】

· · 题解

一维数组f[high]=life

循环d~0

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

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

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

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

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

# include<iostream>
# include<cstring>
# include<algorithm>
using namespace std;
struct p{
    int t,h,l;
}c[101];
int d,g;
int ti[101];
int f[101];
bool cmp(p a,p b)
{
    return a.t<b.t;
}
int main()
{
    cin>>d>>g;
    for(int i=1;i<=g;i++)
      cin>>c[i].t>>c[i].l>>c[i].h;
    sort(c+1,c+1+g,cmp);
    f[0]=10;
    for(int i=1;i<=g;i++)
      for(int j=d;j>=0;j--)
        if(f[j]>=c[i].t)
        {
            if(j+c[i].h>=d)
            {
                cout<<c[i].t;
                return 0;
            }
            f[j+c[i].h]=max(f[j+c[i].h],f[j]);
            f[j]+=c[i].l;
        }
    cout<<f[0];
    return 0;
}