[洛谷1156]垃圾陷阱（DP）

[Luogu1156]

f[i]表示高度为i时的存活时间

Code

#include <cstdio>
#include <algorithm>
#define N 110
using namespace std;

struct info{
	int t,liv,h;
	friend bool operator < (info a,info b){
		return a.t<b.t;
	}
}A[N];
int f[N],dep,n;

inline int read(){
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}

int main(){
	f[0]=10;
	dep=read(),n=read();
	for(int i=1;i<=n;++i) A[i].t=read(),A[i].liv=read(),A[i].h=read();
	sort(A+1,A+n+1);
	for(int i=1;i<=n;++i)
		for(int j=dep;j>=0;--j){//注意倒着循环,否则会覆盖上一轮的状态
			if(f[j]>=A[i].t){
				if(j+A[i].h>=dep){
					printf("%d
",A[i].t);
					return 0;
				}
				f[j+A[i].h]=max(f[j+A[i].h],f[j]);
				f[j]+=A[i].liv;
			}
		}
	printf("%d
",f[0]);
	return 0;
}