1. 题目

传送门= ̄ω ̄=

2. 题解

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

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

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

代码: