解题报告 luogu P1156 【垃圾陷阱】

2018-03-03 17:27:57


这个题非常的像 $01$ 背包,但是又有不同之处,因为 $01$ 背包中的“不装”就不对状态做修改,这里不装则是将垃圾堆起来。

用 $dp[i][j]$ 存储在扔进去 $i$ 个垃圾,高度为 $j$ 时的最大生命值。当 $dp[i][j]=0$ 时,奶牛竟然处于濒死状态,意思是,当生命值恰好为 $0$ 时,奶牛还可以操作垃圾(被这个题这里卡了整整一天。。。)。所以初始化时的 $dp$ 数组要赋负值【 $tip:memset$ 函数中的正数并不是真的赋了那个数,而是一个值比较大的数,这里-1和0均没有影响】

要记得初始化:当扔进去 $0$ 个垃圾,高度为 $0$ 时,奶牛的生命值为 $10$

同样地,要对垃圾数组进行排序,我这里用了重载操作符(注意,可能有同时扔进去的垃圾,但是这里没有特判(可能是数据水了)可以再加一个权值,即当 $a.t==b.t$ 时,继续比较它们的 $h$ ,即吃了能上升的高度)

另:每段时间消耗的能量为 $r[i+1].t-r[i].t$


解说代码: 在背包循环中,如果 $dp[i][j]<0$ ,说明在这个状态奶牛已经死了或者说没有存在过,直接跳过。如果 $dp[i][j]==0$ ,说明这个状态是由别的状态转移而来的,奶牛处于濒死状态,还可以操作,只是一旦回复的能量少于下一段时间的长度,且不能一步跳出去,则当前状态不能转移出去,奶牛死亡。如果状态转移后 $dp$ 值还大于 $0$ ,则正常进行(因为垃圾数组现在是有序的了) $tip2:$ 转移条件一定要是生命 $\ge$ 下一段时间的长度(这里也是很坑的一点)

如果在背包循环中不能跳出,即没有触发 $return 0;$ 说明奶牛跳不出去,此时从头模拟 $sum$ 存储已经用过的能量;当 $m$ (能量)不够继续跳时(这里也要特判),将奶牛剩下的时间(好悲情)加到 $sum$ 中一起输出。

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int max(int x,int y){return x>y?x:y;}
int dp[101][1001];//dp[i][j]表示在扔进去第i个辣鸡,在j的高度时的最大生命
struct trash
{
    int t,f,h;
    friend bool operator <(trash a,trash b)
    {
            return a.t<b.t;
    }
}r[101];
int main()
{
    memset(dp,-1,sizeof(dp));
    int d,g;
    scanf("%d%d",&d,&g);
    for(int i=1;i<=g;i++)
        scanf("%d%d%d",&r[i].t,&r[i].f,&r[i].h);
    sort(r+1,r+g+1);
    dp[0][0]=10;
    r[0].f=0;
    r[0].h=0;
    r[0].t=0;
    for(int i=0;i<g;i++)
        for(int j=0;j<=d;j++)
        {
            if(dp[i][j]<0)//没有奶牛的状态
                continue;
            if(j+r[i+1].h>=d&&dp[i][j]>=r[i+1].t-r[i].t)//转移这个状态时,既满足下一个垃圾可以直接跳出去,又满足奶牛的能量能坚持到下一个垃圾。
            {
                printf("%d\n",r[i+1].t);
                return 0;
            }
            if(dp[i][j]-r[i+1].t+r[i].t>=0)
                dp[i+1][j+r[i+1].h]=dp[i][j]-r[i+1].t+r[i].t;
            if(dp[i][j]-r[i+1].t+r[i].t>=0)
                dp[i+1][j]=max(dp[i+1][j],dp[i][j]-r[i+1].t+r[i].t+r[i+1].f);//这里max因为dp[i+1][j]可能本来有值
        }
    //如果进行到当前状态,说明没能跳出去
    //全吃掉 重新模拟一遍
    //当奶牛不能坚持时,要将现在的能量用完
    int m=10,sum=0;//m是现有能量,sum是已经用过的能量
    for(int i=1;i<=g;i++)
    {
        if(r[i].t-r[i-1].t>m)
        {
            printf("%d\n",sum+m);
            return 0;
        }
        sum+=r[i].t-r[i-1].t;
        m-=r[i].t-r[i-1].t;
        m+=r[i].f;
    }
    printf("%d\n",sum+m);
    return 0;
}