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[1001][101]; struct node{ int t,v,w; bool operator <(const node& y)const{return t<y.t;} }a[101]; inline int g() { R ret=0,fix=1; register char ch; while(!isdigit(ch=getchar())) fix=ch=='-'?-1:fix; do ret=(ret<<3)+(ret<<1)+(ch^48); while(isdigit(ch=getchar())); return fix*ret; } signed main() { V=g(),n=g(); for(R i=1;i<=n;i++) a[i].t=g(),a[i].w=g(),a[i].v=g(); sort(a+1,a+n+1); memset(f,0xcf,sizeof(f));f[0][0]=10; for(R i=1;i<=n;i++) { for(R j=V;j>=a[i].v;j--) { if(f[i-1][j-a[i].v]>=a[i].t-a[i-1].t) f[i][j]=max(f[i][j],f[i-1][j-a[i].v]-(a[i].t-a[i-1].t)); if(f[i-1][j]>=a[i].t-a[i-1].t) f[i][j]=max(f[i][j],f[i-1][j]-(a[i].t-a[i-1].t)+a[i].w); if(j==V&&f[i][j]>=0) {printf("%d ",a[i].t);return 0;} } for(R j=a[i].v-1;j>=0;j--) if(f[i-1][j]>=a[i].t-a[i-1].t) f[i][j]=max(f[i][j],f[i-1][j]-(a[i].t-a[i-1].t)+a[i].w); ret=max(ret,f[i][0]+a[i].t); } printf("%d ",ret); }