解题报告 luogu P1156 【垃圾陷阱】
wjyyy
·
·
题解
这个题非常的像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，则正常进行（因为垃圾数组现在是有序的了）
如果在背包循环中不能跳出，即没有触发$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;
}
```