基础dp

P1156 垃圾陷阱

f[i][j]表示前i个垃圾填j的高度的最大维持时间，一开始觉得这个方程式可以都用来吃从而得到最大时间，但是忘记了j在循环。

#include <bits/stdc++.h>
#include <algorithm>
using namespace std;
#define maxn 1001
#define INF 0x7f7f7f7f
#define max(x,y) x>y?x:y
int f[101][1001],sum;
struct arr{
    int x,t,h;
}a[maxn];
int cmp(arr a,arr b){
    return a.x<b.x;
}
int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    for (int i=1;i<=m;i++){
    	scanf("%d%d%d",&a[i].x,&a[i].t,&a[i].h);
    	sum+=a[i].t;
	}

    sort(a+1,a+m+1,cmp);
    memset(f,0xA0,sizeof f);
    f[0][0]=10; a[0].x=a[0].t=a[0].h=0;
    int fl=0;
    //正的去推正的，这样得出的结果
	// 负的可能推出正的，从而达到顶端
    for (int i=1;i<=m;i++)
    {
        for (int j=0;j<=n;j++)
        {
            if (f[i-1][j]-a[i].x+a[i-1].x>=0)
                f[i][j]=max(f[i][j],f[i-1][j]-a[i].x+a[i-1].x+a[i].t);
            if (f[i-1][j-a[i].h]-a[i].x+a[i-1].x>=0 && j-a[i].h>=0)
			//error if(j-a[i].h>=0)
                f[i][j]=max(f[i][j],f[i-1][j-a[i].h]-a[i].x+a[i-1].x);
            if (f[i][j]>=0 && j==n){
                printf("%d\n",a[i].x);
                fl=1;
                return 0;
            }
        }
    }
    int ans=0;
    if (!fl){
		for(int i=1;i<=m;i++)
			if(f[i][0]>0){
				ans=max(ans,f[i][0]+a[i].x);//在第a[i].x 秒时获得的最大能量，加上之前的a[i].x就是存活时间
			}
		//还能存活的时间+已经存活的时间 a[i].x
		printf("%d\n",ans);
    }
    //为什么不是把东西全吃了，活的最多?
	//因为到下一次吃东西，还要消耗时间/体力
}