题目链接：P1156 垃圾陷阱
大佬推荐的一个题，就尝试做了做，然后就自闭了，相信大佬做的时候直接秒的吧。
首先确定选择顺序，即按放入的时间排序。
容易想到用一维代表选到了第几个垃圾。
考虑分填与吃两种情况，分别更新。
我们容易想到设(dp[i][j])为前(i)个垃圾，堆(j)高度剩下的做多时间。
那么显然可以这样：
[dp[i][j]=max(dp[i][j],dp[i-1][j]-t_i+t_{i-1}+f_i)
]
[dp[i][j]=max(dp[i][j],dp[i-1][j-h_i]-t_i+t_{i-1})
]
当然是保证在合法的情况下。
时间复杂度是(mathcal O(DG))，可以通过本题。
(Code):
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
#define read(x) scanf("%d",&x)
int n,H;
struct node{int t,f,h;}a[105];
int dp[205][205]={0};
bool cmp(node x,node y){return x.t<y.t;}
int main()
{
read(H),read(n);
for(int i=1;i<=n;i++) read(a[i].t),read(a[i].f),read(a[i].h);
sort(a+1,a+n+1,cmp);
for(int i=0;i<=n;i++)
{
for(int j=0;j<=H;j++) dp[i][j]=-100;
}
dp[0][0]=10;
for(int i=1;i<=n;i++)
{
for(int j=0;j<=H;j++)
{
if(dp[i-1][j]>=a[i].t-a[i-1].t) dp[i][j]=max(dp[i][j],dp[i-1][j]-a[i].t+a[i-1].t+a[i].f);
if(j>=a[i].h&&dp[i-1][j-a[i].h]>=a[i].t-a[i-1].t) dp[i][j]=max(dp[i][j],dp[i-1][j-a[i].h]-a[i].t+a[i-1].t);
if(j==H&&dp[i][j]>=0){printf("%d
",a[i].t);return 0;}
}
}
//无法到达，就贪心的吃
int sum=10;
for(int i=1;i<=n;i++)
{
if(sum>=a[i].t) sum+=a[i].f;
else{printf("%d
",sum);return 0;}
}
printf("%d
",sum);
return 0;
}