Description
题目描述了几个状态，我们来理顺一下：
一头牛掉进了坑里，农夫会在几个时段向下扔垃圾，牛初始可以撑10h，对于每一个垃圾，牛可以:
-
把它堆起来，一旦垃圾堆的高度超过\(h\)，她就可以爬出来
-
吃掉它
垃圾好吃吗，并且获得能量值
需要注意的是，牛可以撑到下一次垃圾投放的标准是还能活着的时间\(t\) 大于等于下次垃圾投放的时间\(t'\)，也就是说，每两次垃圾投放会消耗牛\(t_2-t_1\)生命（\(t_2\)代表第二题垃圾投放时间，\(t_1\)代表第一次垃圾投放时间）
如果牛能出去，就输出最早什么时候能爬出，也就是最后一次处理垃圾的投放时间（牛处理垃圾是瞬间的）
Solution
一股强烈的背包气息
我们发现对于每次垃圾投放，牛需要做出如下决策：
- 把它堆在垃圾堆上
- 吃掉
和普通的背包不同，本题需要的参数有：
- 牛的生命值
- 垃圾堆高度
- 牛能爬出去的时间
- 如果不能爬出去，记录牛最多能活多久
参数好多！总不能全都记录，最后MLE吧（
我们再来简化状态。
首先，牛能爬出去的时间是最后一次处理垃圾的时间，而垃圾投放下去牛可以瞬间处理完，所以也就是最后一次垃圾投放牛做决策的时间。
其次，垃圾投放题目并不保证是按照时间顺序输入的，我们需要排序。
但还是没有思路......
我们不妨换个思路，\(f\)数组里只记录牛在多少垃圾投放的时候，垃圾堆高度为多少的时候的最大生命值，因为我们首先要确保牛能出去，再确保利用的垃圾最毕竟垃圾不好吃qwq
这样记录，我们最后只需要判断在出口高度下牛有没有生命值就可以，如果发现有生命值则直接输出最先找到牛有生命值时的垃圾编号，输出它投放的时间即可。
如果牛很惨没出去，我们也只需要输出牛最大能有生命值的时间即可，也就是最大的\(f_{i,j}\),别忘了我们记录的生命值就是时间呀。
需要注意只有牛可以在下一次垃圾投放时活下来我们才转移，也就是\(f_{i-1,j}-trush_{i}.t >=0\)时，这里的\(trush_{i}.t\)表示从小到大排好序的第\(i\)个垃圾投放时间。
我们转移需要进行两次：
-
吃掉该垃圾的转移
-
把垃圾堆起来的转移
我们不能和普通背包一样两种转移合并到一起，本题有两个参数，我们需要确保牛如果在下一次做出该决策她能活着，有的时候可能只能进行一种转移。（当然两个转移是并列的，如果满足当然可以进行两次转移）
因此，我们有两个状态转移方程，分别对应两种决策，如下：
\(f_{i,j}=max(f_{i,j},f_{i-1,j}+trush_i.live(f_{i-1,j} >= trush_i.t)\)
\(f_{i,j}=max(f_{i,j},f_{i-1,j-trush_i.h} (j>=trush_i.h,f_{i-1,j-trush_i.h}>=trush_i.t)\)
Explanation：第一个状态转移方程是吃掉垃圾时的决策，由于下次吃掉垃圾对高度无影响，所以\(j\)不变；第二个状态转移方程是下一次把垃圾堆起来的决策，由于下次堆垃圾对高度有影响，所以上一次高度需要取\(j-trush_{i}.h\),也就是上一次的高度等于本次高度减去本次的垃圾。此外如果想要堆起来必须满足枚举的垃圾堆的高度大于等于垃圾高度，否则会越界。
（PS：需要注意我们每次都是在做现在的决策，之所以说上次下次可能更好理解，需要注意。）
另外，我们需要对\(f\)数组进行初始化，初始化令\(f_{0,0}=10\)即可，因为显然在没有垃圾投放的时候牛初始能撑10h，注意理解题意。
本题的重难点在于如何判断能否转移，能否转移的条件是什么？如何设计状态？
至此，本题得解，代码如下：
Code
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#define N 10010
using namespace std;
int d,g;
struct Node
{
int t,c,h;
}trash[N];
bool cmp(Node a,Node b)
{
return a.t < b.t;
}
int f[N][N];
int maxn = -1;
int main()
{
scanf("%d%d",&d,&g);
for(int i=1;i<=g;i++)
{
scanf("%d%d%d",&trash[i].t,&trash[i].c,&trash[i].h);
}
f[0][0] = 10;
sort(trash+1,trash+g+1,cmp);
for(int i=1;i<=g;i++)
for(int j=0;j<=d;j++)
{
if(f[i-1][j]>=trash[i].t)
f[i][j]=max(f[i][j],f[i-1][j]+trash[i].c);
if(j>=trash[i].h&&f[i-1][j-trash[i].h]>=trash[i].t)
f[i][j]=max(f[i][j],f[i-1][j-trash[i].h]);
}
int maxh=0;
int maxt=0;
int i;
for(i=1;i<=g;i++)
{
for(int j=0;j<=d;j++)
{
if(f[i][j]-trash[i].t>=0)
maxh=max(maxh,j);
maxt=max(maxt,f[i][j]);
}
if(maxh==d)
break;
}
if(maxh==d)
{
cout<<trash[i].t<<endl;
}
else
cout<<maxt<<endl;
return 0;
}