Luogu P1156 垃圾陷阱 DP

f[i][j]表示在第i个垃圾，高度为j的最大生命值

转移分三部分：

　　如果j>=当前垃圾的高度，且两个垃圾间的时间小于等于上一个状态f[i-1][j-a[i].v]的生命值，则可以垫高度

　　如果j>=当前垃圾的高度，且两个垃圾间的时间小于等于上一个状态f[i-1][j]的生命值，则可以吃

　　如果j<当前垃圾的高度，且两个垃圾间的时间小于等于上一个状态f[i-1][j]的生命值，则可以吃

什么时候死的：f[i][0]相当于没有垫高度，拿这个状态再把现在的垃圾吃了，可能是最优解，与ans取一个max就好了

#include<cstdio>

#include<iostream>

#include<cstring>

#include<algorithm>

#include<cmath>

#define R register int

using namespace std;

int V,n,ret=0xcfcfcfcf;

int f[][];

struct node{

    int t,v,w;

    bool operator <(const node& y)const{return t<y.t;}

}a[];

inline int g() {

    R ret=,fix=; register char ch; while(!isdigit(ch=getchar())) fix=ch=='-'?-:fix;

    do ret=(ret<<)+(ret<<)+(ch^); while(isdigit(ch=getchar())); return fix*ret;

}

signed main() {

    V=g(),n=g();

    for(R i=;i<=n;i++) a[i].t=g(),a[i].w=g(),a[i].v=g();

    sort(a+,a+n+);

    memset(f,0xcf,sizeof(f));f[][]=;

    for(R i=;i<=n;i++)

    {

        for(R j=V;j>=a[i].v;j--) {

            if(f[i-][j-a[i].v]>=a[i].t-a[i-].t) f[i][j]=max(f[i][j],f[i-][j-a[i].v]-(a[i].t-a[i-].t));

            if(f[i-][j]>=a[i].t-a[i-].t) f[i][j]=max(f[i][j],f[i-][j]-(a[i].t-a[i-].t)+a[i].w);

            if(j==V&&f[i][j]>=) {printf("%d\n",a[i].t);return ;}

        }

        for(R j=a[i].v-;j>=;j--) if(f[i-][j]>=a[i].t-a[i-].t) f[i][j]=max(f[i][j],f[i-][j]-(a[i].t-a[i-].t)+a[i].w);

        ret=max(ret,f[i][]+a[i].t);

    }

    printf("%d\n",ret);

}

---