洛谷$1156$ 垃圾陷阱 $dp$

(Sol)

(f_{i,j})前(i)个垃圾,能活到时间(j)的最高垃圾高度.(t_i)表示第(i)个垃圾掉落的时间,(g_i)表示吃垃圾(i)能维持的时间,(h_i)表示堆垃圾(i)的高度.

(f_{i,j}=max{f_{i-1,j}+h_i,f_{i-1,j-g_i}}).

注意初始化和转移的条件.初始化为(-1),第一个转移的条件是(f_{i-1,j}!=-1),第二个转移的条件是(j-g_igeq t_i).

(Code)

#include<bits/stdc++.h>
#define il inline
#define Ri register int
#define go(i,a,b) for(Ri i=a;i<=b;++i)
#define yes(i,a,b) for(Ri i=a;i>=b;--i)
#define mem(a,b) memset(a,b,sizeof(a))
using namespace std;
il int read()
{
    Ri x=0,y=1;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')y=-1;c=getchar();}
    while(c>='0'&&c<='9'){x=(x<<1)+(x<<3)+c-'0';c=getchar();}
    return x*y;
}
int dep,n,f[105][3005],as=3001;
struct nd{int t,g,h;}a[105];
il bool cmp(nd x,nd y){return x.t<y.t;}
int main()
{
	dep=read(),n=read();
	go(i,1,n)a[i]=(nd){read(),read(),read()};
	sort(a+1,a+n+1,cmp);
	mem(f,-1);go(j,0,10)f[0][j]=0;
	go(i,1,n)
	{
		go(j,a[i].t,3000)
	    {
			if(f[i-1][j]>-1)f[i][j]=max(f[i][j],f[i-1][j]+a[i].h);
			if(j-a[i].g>=a[i].t)f[i][j]=max(f[i][j],f[i-1][j-a[i].g]);
	    }
	}
	go(i,1,n)go(j,0,3000)if(f[i][j]>=dep){as=min(as,j);break;}
	if(as<3001){printf("%d
",as);return 0;}as=0;
	go(i,1,n)yes(j,3000,0)if(f[i][j]>-1){as=max(as,j);break;}
	printf("%d
",as);return 0;
}