题目描述

卡门――农夫约翰极其珍视的一条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 45 4 99 3 212 6 1013 1 1

输出样例#1： 

13

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

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

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

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

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

int cmp(qwq a,qwq b){    return a.t

数组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 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #define maxi 0x7fffffffusing 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
          
           =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~