这题算是一道比较神奇的背包，记一下。

思路

这道题很明显叫我们用时间换高度，而换的条件还是时间，就很烦。

因此考虑使 fif_i 表示高度 ii 可以活的最久时间，用刷表法，当第一次刷到 ⩾\geqslant 目标高度时说明我们第一次可以活在目标，成功了。

转移的式子在有了逆向的思路后是很好想的：

f[j+nl[i].d]=max(f[j],f[j+nl[i].d]);
f[j]+=nl[i].l;

代码

const int maxn=152;
int dep,n,f[maxn],ans;
struct garage
{
    int t,l,d;
}nl[maxn];
inline bool cmp(garage x,garage y)
{
    return x.t<y.t;
}
int main()
{
    dep=in();n=in();
    fru(i,1,n)
    {
        nl[i].t=in();
        nl[i].l=in();
        nl[i].d=in();
    }
    memset(f,-0x3f,sizeof f);
    f[0]=10;
    sort(nl+1,nl+n+1,cmp);
    fru(i,1,n)
    {
        frd(j,dep,0)
        if(f[j]>=nl[i].t)
        {
            if(j+nl[i].d>=dep)
            {
                out(nl[i].t);
                return 0;
            }
            f[j+nl[i].d]=max(f[j],f[j+nl[i].d]);
            f[j]+=nl[i].l;
        }
    }
    out(f[0]);
    return 0;
}