题解 P1156 【垃圾陷阱】

· · 题解

上次终于发了篇题解，好嗨森

作为一名蒟蒻，其实我也搞不清楚这是什么DP但是还是硬打了

这道题首先有三个关键量，垃圾数量、奶牛的当前生命、当前高度

我们可以把他们当中的两个作为数组下标，一个作为值

我们一般把有限值作为下标

垃圾数量和当前高度都是有限的，而生命值却有可能很大（这个奶牛可能只会吃）

所以f[i][j]为第i个垃圾j高度的最大生命

还有一件事我们要把垃圾按扔下来的时间排好序

在DP过程中只要超过高度我们就可以输出了

代码中还有点解释

C++AC代码如下

#include<bits/stdc++.h>
using namespace std;
int f[101][101],d,g,ans;
struct laji{
    int T,F,H;
}a[101];//结构体存储垃圾的有关数据
//T,F,H和题干中的一样
bool cmp(laji i,laji j){
    return i.T<j.T;
}
int main(){
    cin>>d>>g;
    for(int i=1;i<=g;i++) scanf("%d%d%d",&a[i].T,&a[i].F,&a[i].H);
    sort(a+1,a+1+g,cmp);
    f[0][0]=10;//初始化为f[0][0]=10，因为他一开始能活10个小时
    for(int i=1;i<=g;i++){
        for(int j=0;j<d;j++){//这个垃圾用来吃
            if(a[i].T<=f[i-1][j]) f[i][j]=f[i-1][j]+a[i].F;
            //if判断的作用是它活到了这个垃圾
        }
        for(int j=0;j<d;j++){//这个垃圾用来堆
            if(a[i].T<=f[i-1][j])//它活到了这个垃圾
            if(j+a[i].H>=d){//它已经可以逃出生天了
                cout<<a[i].T;
                return 0;
            }
            f[i][j+a[i].H]=max(f[i][j+a[i].H],f[i-1][j]);//他还逃不出
        }
    }
    for(int i=1;i<=g;i++){//很遗憾他最后还是没有逃出去
    //计算它最多能活多少时间
        for(int j=0;j<d;j++) ans=max(ans,f[i][j]);
    }
    cout<<ans;
    return 0;
}

最后说一句，FJ家的奶牛无敌了