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;
}
分类: 所有

XZYQvQ

炒鸡辣鸡的制杖蒟蒻一枚QvQ

发表评论

电子邮件地址不会被公开。 必填项已用*标注

你是机器人吗? =。= *