P1156 垃圾陷阱网页链接添加链接描述题目描述卡门――农夫约翰极其珍视的一头Holsteins奶牛――已经落到了 “垃圾井” 中。“垃圾井” 是农夫们扔垃圾的地方它的深度为D DD2 ≤ D ≤ 100 2 \le D \le 1002≤D≤100英尺。卡门想把垃圾堆起来等到堆得与井深同样高或比井深更高即垃圾高度总和≥ D \geq D≥D时她就能逃出井外了。另外卡门可以通过吃一些垃圾来维持自己的生命。每个垃圾都可以用来吃或堆放并且堆放垃圾不用花费卡门的时间。假设卡门预先知道了每个垃圾扔下的时间t tt1 ≤ t ≤ 1000 1 \le t \le 10001≤t≤1000以及每个垃圾堆放的高度h hh1 ≤ h ≤ 25 1 \le h \le 251≤h≤25和吃进该垃圾能增加维持生命的时间f ff1 ≤ f ≤ 30 1 \le f \le 301≤f≤30要求出卡门最早能逃出井外的时间已知卡门当前体内有足够持续10 1010小时的能量如果卡门10 1010小时内不含10 1010小时维持生命的时间同没有进食卡门就将饿死。特别地若体力值为0 00时吃下垃圾或逃出井外也不会饿死。输入格式第一行为两个整数D DD和G GG1 ≤ G ≤ 100 1 \le G \le 1001≤G≤100G GG为被投入井的垃圾的数量。第二到第G 1 G1G1行每行包括三个整数t tt1 ≤ t ≤ 1000 1 \le t \le 10001≤t≤1000表示垃圾被投进井中的时间f ff1 ≤ f ≤ 30 1 \le f \le 301≤f≤30表示该垃圾能维持卡门生命的时间和h hh1 ≤ h ≤ 25 1 \le h \le 251≤h≤25该垃圾能垫高的高度。输出格式如果卡门可以爬出陷阱输出一个整数表示最早什么时候可以爬出否则输出卡门最长可以存活多长时间。输入输出样例 #1输入 #120 4 5 4 9 9 3 2 12 6 10 13 1 1输出 #113说明/提示【样例说明】卡门堆放她收到的第一个垃圾h e i g h t 9 \mathrm{height}9height9卡门吃掉她收到的第2 22个垃圾使她的生命从10 1010小时延伸到13 1313小时卡门堆放第3 33个垃圾h e i g h t 19 \mathrm{height}19height19卡门堆放第4 44个垃圾h e i g h t 20 \mathrm{height}20height20。解题思路本题是动态规划背包问题的经典变形。奶牛卡门掉入深度为D DD的井中有G GG个垃圾在不同时间t tt被投入每个垃圾可以选择吃掉增加存活时间f ff或堆放增加高度h hh。卡门初始拥有10 1010小时能量若存活时间耗尽则死亡。目标是求出她最早能爬出井外高度≥ D \ge D≥D的时间若无法逃出则输出最长存活时间。1. 问题等价转化将垃圾按投入时间t tt升序排序因为垃圾只能按时间顺序到达。定义状态f[j]表示当前堆放垃圾总高度为j jj时卡门能够存活的最大时间。初始时f[0] 10初始能量其余高度不可达可设为负无穷或 0但代码中利用f[j] c[i].t来判断可达性。对于每个垃圾i ii时间t i t_iti​高度h i h_ihi​生命加成l i l_ili​在到达时若卡门仍存活即f[j] t_i则有两种选择堆放新高度为j h i j h_ijhi​。若j h i ≥ D j h_i \ge Djhi​≥D则卡门立即逃出最早逃出时间就是t i t_iti​直接输出并结束。否则新状态的存活时间仍为f[j]因为堆放不消耗时间更新f[j h_i] max(f[j h_i], f[j])。吃掉存活时间增加l i l_ili​即f[j] l_i。由于每个垃圾只能使用一次采用0/1 背包的倒序遍历高度j jj从D DD到0 00确保每个垃圾不会被重复选择。若所有垃圾处理完后仍无法逃出则最长存活时间就是卡门吃掉所有能吃的垃圾后的存活时间。由于堆放垃圾会减少可吃的垃圾数量为了最大化存活时间她应放弃所有堆放只吃垃圾。因此最终答案就是f[0]高度为 0 时的最大存活时间。2. 算法实现输入与排序读入D , G D, GD,G将每个垃圾的信息存入结构体数组c按时间t tt升序排序。初始化f[0] 10其余f[j]初始为 0或负值但代码中通过f[j] c[i].t判断可达未可达时f[j]为 0而t 1所以不会误判。动态规划外层循环遍历每个垃圾i1 ∼ G 1 \sim G1∼G。内层循环高度j从D DD递减到0 00若f[j] c[i].t当前状态存活若j c[i].h D输出c[i].t并结束程序。否则更新f[j c[i].h] max(f[j c[i].h], f[j])堆放。然后更新f[j] c[i].l吃掉。输出若循环结束仍未逃出输出f[0]即最长存活时间。3. 复杂度分析时间复杂度O ( G × D ) O(G \times D)O(G×D)。G ≤ 100 G \le 100G≤100D ≤ 100 D \le 100D≤100总运算量约10 4 10^4104非常小。空间复杂度O ( D ) O(D)O(D)仅需一维 DP 数组。总结将问题抽象为“高度”维度的背包 DPf[j]表示达到高度j jj时的最大存活时间。通过倒序遍历保证每个垃圾只使用一次并实时判断能否逃出。若无法逃出最优策略是全部吃掉以延长生命因此答案为f[0]。算法简洁高效完美解决了此问题。代码简要说明结构体P存储每个垃圾的时间t、高度h、生命加成l。数组f[101]f[j]表示堆放高度为j时的最大存活时间初始f[0] 10。排序按t升序排列垃圾。DP 循环外层i遍历垃圾。内层j从d递减到0。若f[j] c[i].t存活若j c[i].h d输出c[i].t并返回。否则更新f[j c[i].h] max(f[j c[i].h], f[j])。更新f[j] c[i].l。输出若未逃出输出f[0]。代码内容#includebits/stdc.husingnamespacestd;#defineendl\ntypedeflonglongll;typedefunsignedlonglongull;typedefvectorvectorllvvt;typedefpairll,llpll;constll N1e310;constll INF1e18;constll M1e610;constll mod1e97;structP{ll t,h,l;}c[101];ll d,g;ll ti[101];ll f[101];boolcmp(P a,P b){returna.tb.t;}intmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);cindg;for(ll i1;ig;i)cinc[i].tc[i].lc[i].h;sort(c1,c1g,cmp);f[0]10;for(ll i1;ig;i){for(ll jd;j0;j--){if(f[j]c[i].t){if(jc[i].hd){coutc[i].t;return0;}f[jc[i].h]max(f[jc[i].h],f[j]);f[j]c[i].l;}}}coutf[0];return0;}