洛谷p1156 垃圾陷阱（蒟蒻手把手教你用01背包把这道题复杂化）

手把手教你用01背包把这道题复杂化）"/>

洛谷p1156 垃圾陷阱（蒟蒻手把手教你用01背包把这道题复杂化）

题目描述

卡门――农夫约翰极其珍视的一条Holsteins奶牛――已经落了到“垃圾井”中。“垃圾井”是农夫们扔垃圾的地方，它的深度为D(2<=D<=100)英尺。

卡门想把垃圾堆起来，等到堆得与井同样高时，她就能逃出井外了。另外，卡门可以通过吃一些垃圾来维持自己的生命。

每个垃圾都可以用来吃或堆放，并且堆放垃圾不用花费卡门的时间。

假设卡门预先知道了每个垃圾扔下的时间t(0< t<=1000)，以及每个垃圾堆放的高度h(1<=h<=25)和吃进该垃圾能维持生命的时间f(1<=f<=30)，要求出卡门最早能逃出井外的时间，假设卡门当前体内有足够持续10小时的能量，如果卡门10小时内没有进食，卡门就将饿死。

输入输出格式

输入格式：

第一行为2个整数，D 和 G (1 <= G <= 100)，G为被投入井的垃圾的数量。

第二到第G+1行每行包括3个整数：T (0 < T <= 1000)，表示垃圾被投进井中的时间；F (1 <= F <= 30)，表示该垃圾能维持卡门生命的时间；和 H (1 <= H <= 25)，该垃圾能垫高的高度。

输出格式：

如果卡门可以爬出陷阱，输出一个整表示最早什么时候可以爬出；否则输出卡门最长可以存活多长时间。

输入输出样例

输入样例#1：  复制

20 4
5 4 9
9 3 2
12 6 10
13 1 1

输出样例#1：  复制

13

看到题发现是两个状态一开始就吓懵了(:3J∠)

第一反应就是01背包取与不取的问题，吃不吃辣鸡和堆不堆辣鸡

当然，生命我所欲也，高度亦我所欲也，二者不可兼得，舍高度而取生命者也，生命和高度只能二选一。

其实也可以很皮的两个都不选（小声bb）**

首先，因为时间是（应该或许大概）随机的啦，所以先按时间排个序(´・ω・`)

int cmp(qwq a,qwq b)
{return a.t<b.t;
}sort(laji+1,laji+1+n,cmp);

数组f[h][t]记录的是状态（当前堆了高度为h的辣鸡，生命能取到t个小时）能否取到。

然后就是炒鸡炒鸡炒鸡重要的动态转移啦 (•ㅂ•)/♥（敲黑板.jpg）

    f[0][10]=true;//初状态没有堆的辣鸡，可以活十个小时所以f【0】【10】是取的到的maxt=10;//maxt记录的是当前时间最大值for(int i=1;i<=n;++i)//疯狂枚举每一堆辣鸡{int st=laji[i].t,sf=laji[i].f,sh=laji[i].h;maxt+=sf;for(int j=H+sh;j>=0;--j)//疯狂枚举高度{for(int k=maxt+st;k>=0;--k)//疯狂枚举时间，因为是01背包，每个辣鸡的时间和高度都只能取一次所以j，k是递减的ww{if(!f[j][k]&&k>=sf+st)//第i堆辣鸡拿来吃了，k>=sf+st判断枚举的这个时间在第i堆辣鸡到来时卡门是否还活着{f[j][k]=f[j][k-sf];}if(!f[j][k]&&j>=sh&&k>=st)//第i堆辣鸡堆起来了，同理需判断卡门是否还活着{f[j][k]=f[j-sh][k];if(f[j][k])if(j>=H)mint=min(mint,st);//更新爬出去的时候时间最小值}}}}

然后就输出结果啦~(≖ ‿ ≖)✧

顺带一提最大存活时间不是所有时间和啦，因为所有辣鸡可能还不够吃2333，就会导致卡门爬坑未半而中道崩殂

    if(mint!=maxi)//如果被更新过说明卡门爬出去了直接输出时间最小值{printf("%d",mint);return 0;}for(int i=maxt;i>=1;--i)//如果没有就输出存活最长时间（心疼卡门1s）{if(f[0][i]){printf("%d",i);return 0;}}

阿啦这道题很多做法啦，看了dalao们的题解感觉自己的做法超暴力qwq

后排献上超辣鸡的完整代码quq

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#define maxi 0x7fffffff
using namespace std;int H,n,maxt,mint=maxi;
bool f[150][2000];struct qwq
{int t;int f;int h;
}laji[105];int cmp(qwq a,qwq b)
{return a.t<b.t;
}int main()
{scanf("%d%d",&H,&n);for(int i=1;i<=n;++i){scanf("%d%d%d",&laji[i].t,&laji[i].f,&laji[i].h);}sort(laji+1,laji+1+n,cmp);f[0][10]=true;maxt=10;for(int i=1;i<=n;++i){int st=laji[i].t,sf=laji[i].f,sh=laji[i].h;maxt+=sf;for(int j=H+sh;j>=0;--j){for(int k=maxt+st;k>=0;--k){if(!f[j][k]&&k>=sf+st){f[j][k]=f[j][k-sf];}if(!f[j][k]&&j>=sh&&k>=st){f[j][k]=f[j-sh][k];if(f[j][k])if(j>=H)mint=min(mint,st);}}}}if(mint!=maxi){printf("%d",mint);return 0;}for(int i=maxt;i>=1;--i){if(f[0][i]){printf("%d",i);return 0;}}return 0;
}

好啦没p放了，over~