1. 题目

传送门＝￣ω￣＝

2. 题解

记忆化非递归式深搜。。。
首先说下这题很坑的地方：它没说垃圾按照丢下来的时间排序，所以需要自行排序。。。我被这个坑了很久。。。
设 $book(i,j,k)$表示状态（当前牛的深度为 $i$，生命值为 $j$，现在正在丢第 $k$个垃圾）是否访问过。
如果访问过，直接 return。
最多有 $100×3000×100$个状态，因此可以用 $28.6102294921875$MB 的内存存下。

当 $i<=0$时，更新 $ans$。一开始 $ans$设置为 $inf$，最后完成深搜以后判断 $ans$是否等于 $inf$，如果等于则计算最久存活时间。否则输出 $ans$。

计算最久存活时间的话，直接不往上跳，每次有垃圾就吃，计算最后能活多久即可。

代码：

#include <bits/stdc++.h>
using namespace std;
struct node{int t,f,h;bool operator<(node k)const{return t<k.t;}}p[105];
int d,g,ans=INT_MAX;
bool book[105][3005][105];
void dfs(int dep,int liv,int cnt)
{
    if(cnt>g||liv<p[cnt].t)return;
    if(book[dep][liv][cnt])return;
    book[dep][liv][cnt]=1;
    dfs(dep,liv+p[cnt].f,cnt+1);
    if(dep-p[cnt].h<=0){ans=min(ans,p[cnt].t);return;}
    dfs(dep-p[cnt].h,liv,cnt+1);
}
int main()
{
    scanf("%d%d",&d,&g);
    for(int i=1;i<=g;i++)scanf("%d%d%d",&p[i].t,&p[i].f,&p[i].h);
    sort(p+1,p+1+g,less<node>()),dfs(d,10,1);
    if(ans==INT_MAX)
        {ans=10;for(int i=1,liv=10;i<=g&&ans>=p[i].t;ans+=p[i++].f);}
    printf("%d\n",ans);
    return 0;
}