#（抽象背包）洛谷P1156 垃圾陷阱（提高+/省选

抽象背包）洛谷P1156 垃圾陷阱（提高+/省选"/>

#（抽象背包）洛谷P1156 垃圾陷阱（提高+/省选

题目描述

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

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

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

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

输入格式

第一行为22个整数，DD和 G (1 \le G \le 100)G(1≤G≤100)，GG为被投入井的垃圾的数量。

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

输出格式

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

输入输出样例

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

13

说明/提示

[样例说明]

卡门堆放她收到的第一个垃圾：height=9height=9；

卡门吃掉她收到的第22个垃圾，使她的生命从1010小时延伸到1313小时；

卡门堆放第33个垃圾，height=19height=19；

卡门堆放第44个垃圾，height=20height=20。

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

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

要记得初始化：当扔进去00个垃圾，高度为00时，奶牛的生命值为1010

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

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

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

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

#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;
}

转载于:.html