记录编号	79565	评测结果	AAAAAAAAAA
题目名称	596.垃圾陷阱	最终得分	100
用户昵称	digital-T	是否通过	通过
代码语言	C++	运行时间	0.003 s
提交时间	2013-11-05 22:02:29	内存使用	0.31 MiB

#include<fstream>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
ifstream fi("well.in");
ofstream fo("well.out");
const int INF=0x7FFFFFFF;
int D,G,dp[101];
class gar
{
public:
	int T,F,H;
}g[101];
bool op(gar x,gar y){return x.T<y.T;}
int main()
{
	fi>>D>>G;
	for(int i=1;i<=G;i++)fi>>g[i].T>>g[i].F>>g[i].H;
	sort(g+1,g+G+1,op);
	bool boo;
	memset(dp,0,sizeof(dp));
	dp[0]=10;//爬到j高度时最大的剩余存活时间
	for(int i=1;i<=G;i++)
	{
		boo=false;
		for(int j=D;j>=0;j--)
		if(dp[j]>=g[i].T)
		{
			if(j+g[i].H>=D)
			{
				fo<<g[i].T<<endl;
				goto NEXT;
			}
			if(dp[j]>dp[j+g[i].H])
				dp[j+g[i].H]=dp[j];
			dp[j]+=g[i].F;
			boo=true;
		}
		if(!boo)break;
	}
	fo<<dp[0]<<endl;
	NEXT:;
	return 0;
}