记录编号	79540	评测结果	AAAAAAAAAA
题目名称	垃圾陷阱	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	0.003 s
提交时间	2013-11-05 21:33:06	内存使用	0.47 MiB

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
//f[i][j]表示投入第i个垃圾后高度为j的最大剩余生命值,其中T=i表示可以使用i时刻之前的一切垃圾
//①把这个垃圾摞起来:用f[i-1]中的每个状态去更新:f[i-1][j]-(两个垃圾的时间差)->f[i][j+这个垃圾的高度]
//②壮士干了这碗热翔:用f[i-1]中的每个状态去更新:f[i-1][j]+(这个垃圾的时间)->f[i][j]
//每次转移O(D),共转移G次
const int SIZED=200,SIZEG=200;
int D,G;//深度和垃圾数量
int dp[SIZEG][SIZED]={0};
int maxheight[SIZEG]={0};
class RUBBISH{
public:
	int t,f,h;
	//投入时间,能维持生命时间,垫高高度
};
RUBBISH rub[SIZEG];
bool operator < (RUBBISH a,RUBBISH b){
	return a.t<b.t;
}
void DP(void){
	int i,j;
	for(i=0;i<=G;i++){
		for(j=0;j<=100;j++) dp[i][j]=-1;
	}
	rub[0].t=0;
	maxheight[0]=0;
	dp[0][0]=10;
	int nowh,nowf,dt;
	bool survive;
	for(i=1;i<=G;i++){
		survive=false;
		dt=rub[i].t-rub[i-1].t;
		nowh=rub[i].h;
		nowf=rub[i].f;
		//转移摞起来的
		for(j=0;j<=maxheight[i-1];j++){
			if(dp[i-1][j]-dt>=0){//没饿死
				dp[i][j+nowh]=max(dp[i][j+nowh],dp[i-1][j]-dt);
				survive=true;
				maxheight[i]=max(maxheight[i],j+nowh);
			}
		}
		//转移干热翔的
		for(j=0;j<=maxheight[i-1];j++){
			if(dp[i-1][j]-dt>=0){//没饿死
				dp[i][j]=max(dp[i][j],dp[i-1][j]-dt+nowf);
				survive=true;
				maxheight[i]=max(maxheight[i],j+nowh);
			}
		}
		if(!survive){
			break;
		}
		if(maxheight[i]>=D){
			printf("%d\n",rub[i].t);
			return;
		}
	}
	int sum=0;
	for(j=1;j<i;j++){
		sum+=rub[j].f;
	}
	printf("%d\n",sum+10);
}
void read(void){
	scanf("%d%d",&D,&G);
	int i;
	for(i=1;i<=G;i++) scanf("%d%d%d",&rub[i].t,&rub[i].f,&rub[i].h);
}
int main(){
	freopen("well.in","r",stdin);
	freopen("well.out","w",stdout);
	read();
	sort(rub+1,rub+1+G);
	DP();
	/*for(int i=0;i<=G;i++){
		for(int j=0;j<=10;j++) cout<<dp[i][j]<<" ";
		cout<<endl;
	}*/
	return 0;
}