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

这个题非常的像$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$中一起输出。 ```cpp #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; } ```