题解 P1156 【垃圾陷阱】

· · 题解

这道题蒟蒻调了大半天。。这篇题解包含了我自己在做这道题过程中出现的错误思路代码和思路历程，可以帮助更好的理解这道题深层的dp思想，对dp不熟的或想不出来的可以看看这篇题解~~

1.首先看到这道题的时候我的脑子里立刻闪现出了一个dp思路，即f[i][j][k]表示前i个物品高度为j，血量为k的最少时间，显然这样是会爆空间的，于是我又想到通过滚动数组滚动i来优化空间，但是这样时间复杂度为O(ijk)，并且最后还要枚举j，k来寻找答案，于是我就放弃了这个做法

2.于是我们考虑一种二维做法；我们可以让时间作为判断转移的依据，则可以优化一维f[i][j]表示前i个物品摞到j高度的最大血量，再滚动一下i维，这样时间复杂度较低，于是我非常开心的写了下面的错误代码；

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
int d,n,f[130],ti[110],ans=-1;
struct ren{
    int t,e,h;
}a[110];
bool cmp(ren a,ren b){
    return a.t<b.t;
}
int main(){
    cin>>d>>n;
    for(int i=1;i<=n;i++)cin>>a[i].t>>a[i].e>>a[i].h;
    sort(a+1,a+n+1,cmp);
    for(int i=1;i<=n;i++)ti[i]=a[i].t-a[i-1].t;
    memset(f,-0x3f,sizeof(f));
    f[0]=10;
    for(int i=1;i<=n;i++)
        for(int j=d+25;j>=0;j--){
            if(j-a[i].h>=0&&f[j-a[i].h]>=0)f[j]=max(f[j],f[j-a[i].h]-ti[i]);
            if(f[j]-ti[i]>=0)f[j]=max(f[j],f[j]-ti[i]+a[i].e);
            if(j>=d&&f[j]>=0){cout<<a[i].t;return 0;}
            if(f[j]>=0)ans=max(ans,f[j]+a[i].t);
        }
    cout<<ans;
    return 0;
}

可以发现与二维正解不同的是，我想到的是用f存储现在时间剩余的血量，而不是一共有的总血量最后交上去打了18分，，，，于是我开始苦思这里的思路哪里不对，这里举一个例子；

假设我的第一堆垃圾是这样的:时间=6；能量=4；即等这堆垃圾需要的能量小于吃这堆垃圾得到的能量，那么f[0]不会更新而一直会为10，即它不会去吃这样的垃圾，这样显然在一些情况下是不优的，当然这个思路bug还有很多，这里只说一个易懂的错误；

3.于是我又想到，如果让f存储的能量是总的累积的能量，即不考虑流失的能量，f不会变小，最后在用现在的时间比较判断，那么上面类似的bug就不会出现，这也就是二维思路的正解啦~~ 下面上ac代码 我尽量备注，不懂得可以私信问我；

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
int d,n,f[130];
struct ren{
    int t,e,h;
}a[110];
bool cmp(ren a,ren b){
    return a.t<b.t;
}
int main(){
    cin>>d>>n;
    for(int i=1;i<=n;i++)cin>>a[i].t>>a[i].e>>a[i].h;
    sort(a+1,a+n+1,cmp);//按时间排序
    f[0]=10;
    for(int i=1;i<=n;i++)
        for(int j=d;j>=0;j--){
            if(f[j]>=a[i].t)f[j]=max(f[j],f[j]+a[i].e);
            //吃的这种情况要放在前面，否则判断所用的f[j]会被堆的情况更新
            if(j-a[i].h>=0&&f[j-a[i].h]>=a[i].t){
                f[j]=max(f[j],f[j-a[i].h]);
                if(j>=d){cout<<a[i].t;return 0;}
            }
        }
    cout<<f[0];//最长存活时间；
    return 0;
}