P1156 垃圾陷阱

先将垃圾按时间排序

分类讨论

先假设能逃出去

设f[i][j]表示前i个垃圾叠成高度j时的最长生存时间

初始f[0][0]=10

类背包转移

注意濒死也是能转移的，即f[][]<0才无法转移

转移时超过高度就输出当前时间

再模拟逃不出去

计算最长存活时间

#include <bits/stdc++.h>
using namespace std;
template<class t> inline t read(t &x){
    x=0;char c=getchar();bool f=0;
    while(!isdigit(c)) f|=c=='-',c=getchar();
    while(isdigit(c)) x=(x<<1)+(x<<3)+(c^48),c=getchar();
    if(f) x=-x;return x;
}
template<class t> inline void write(t x){
    if(x<0){putchar('-'),write(-x);}
    else{if(x>9)write(x/10);putchar('0'+x%10);}
}
const int N=105,M=105;
int n,m,f[N][M];
struct trash{
    int t,f,h;
    inline bool operator < (const trash &nt) const {
        return t<nt.t;
    }
}a[N];
signed main(){
    read(m);read(n);
    for(int i=1;i<=n;i++){
        read(a[i].t);
        read(a[i].f);
        read(a[i].h);
    }
    sort(a+1,a+1+n);
    memset(f,-1,sizeof f);
    f[0][0]=10;
    for(int i=1;i<=n;i++){
        for(int j=0;j<=m;j++) if(f[i-1][j]>=0){
            if(j+a[i].h>=m&&f[i-1][j]+a[i-1].t>=a[i].t){
                write(a[i].t);
                return 0;
            }
            if(f[i-1][j]+a[i-1].t>=a[i].t){
                f[i][j+a[i].h]=f[i-1][j]+a[i-1].t-a[i].t;
                f[i][j]=max(f[i][j],f[i-1][j]+a[i-1].t-a[i].t+a[i].f);
            }
        }
    }
    m=10;
    for(int i=1;i<=n;i++){
        if(m+a[i-1].t<a[i].t){
            write(m+a[i-1].t);
            return 0;
        }
        m-=a[i].t-a[i-1].t;
        m+=a[i].f;
    }
    write(m+a[n].t);
}