题解 P1156 【垃圾陷阱】

· · 题解

码了10min查了2h的错。。。被坑到绝望

==============================================================

直接无脑上记忆化搜索，如下情况退出函数：

1.当前垃圾掉下来的时候牛已经凉了（注意当牛的最大存活时间==当前时间时牛还是活着的）

2.堆上当前垃圾牛就出去了（h+g[i]>=m）

3.没垃圾了（牛迟早要凉对吧）

否则要么吃掉当前垃圾要么堆上当前垃圾取个min

如果出不去就把所有垃圾吃掉

详见代码

==============================================================

坑点：

1.垃圾不是按时间顺序给出的，要排序

2.如果出不去的话不能无脑把所有垃圾的存活时间加起来，要注意下一个垃圾掉下来的时候牛是不是已经凉了

==============================================================

代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int n,m,dp[110][1010][110];
struct node{int tim,f,g;}a[110];
int cmp(const node &x,const node &y){return x.tim<y.tim;}
int dfs(int x,int t,int h){
    if (x>n||t<a[x].tim) return 0x3f3f3f3f;//没垃圾了或者牛凉了 inf表示出不去 
    if (h+a[x].g>=m) return a[x].tim;//牛出去了 
    if (dp[x][t][h]) return dp[x][t][h];
    return dp[x][t][h]=min(dfs(x+1,t+a[x].f,h),dfs(x+1,t,h+a[x].g));//转移 
}
int main()
{
    scanf("%d%d",&m,&n);
    for (int i=1;i<=n;++i) scanf("%d%d%d",&a[i].tim,&a[i].f,&a[i].g);
    sort(a+1,a+n+1,cmp);//坑 
    if (dfs(1,10,0)!=0x3f3f3f3f) printf("%d\n",dp[1][10][0]);
    else{
        int ans=10;
        for (int i=1;i<=n;++i)
            if (ans<a[i].tim) break;//坑 
            else ans+=a[i].f;
        printf("%d\n",ans);
    }
    return 0;
}