垃圾陷阱

#include<cstdio>
#include<algorithm>
using namespace std;
struct item
{
int t,h,f;
bool operator < (const item& x) const
{
return t<x.t;
}
};
int D,G,rest_time[100],ans,longest;
item junk[100];
bool escape=false;
/*_init()
{
item rest;
if(item.h<=item.h)
return 0
}*/
int main()
{
scanf("%d%d",&D,&G);
for(int i=0;i<G;i++)
scanf("%d%d%d",&junk[i].t,&junk[i].f,&junk[i].h);
sort(junk,junk+G);
rest_time[0]=10;
for(int i=0;i<G;i++)
{
for(int j=0;j<D;j++)
{
rest_time[j]-=junk[i].t;
if(i>0)
rest_time[j]+=junk[i-1].t;
}
for(int j=D-1;j>=0;j--)
if(rest_time[j]>=0)
{
if(j+junk[i].h<D)
rest_time[j+junk[i].h]=max(rest_time[j+junk[i].h],rest_time[j]);
else

{
escape=true;
ans=junk[i].t;
break;
}
rest_time[j]+=junk[i].f;

}
if(escape)
break;
}
printf("%d\n",escape?ans:junk[G-1].t+rest_time[0]);
return 0;
}

垃圾陷阱

原文：http://www.cnblogs.com/lutongxi/p/5991767.html