P1156 垃圾陷阱
斯德哥尔摩
2018-10-14 16:58:07
[P1156 垃圾陷阱](https://www.luogu.org/problemnew/show/P1156)
一眼看出是道背包题。
设$dp[i]$表示当堆到$i$高度时的生命是多少。
像背包一样，物品正着循环，高度倒着循环。
设枚举到第$i$个物品，当前枚举到的高度为$j$。
如果$dp[j]>=t_i$，分两种情况：
1. $j+h_i>=d$，就直接输出这个垃圾丢下来的时间，并结束程序。
2. $dp[j+h_i]=\max\{dp[j]\}$，即不吃这个垃圾，而用它来堆高度。
3. $dp[j]+=f_i$，即吃掉这个垃圾。
最后输出$dp[0]$，即出不去时，能存活的最长时间。
附代码：
```cpp
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#define MAXN 110
using namespace std;
int n,m,dp[MAXN];
struct Rubbish{
int t,f,h;
friend bool operator <(const Rubbish &p,const Rubbish &q){
return p.t<q.t;
}
}a[MAXN];
inline int read(){
int date=0,w=1;char c=0;
while(c<'0'||c>'9'){if(c=='-')w=-1;c=getchar();}
while(c>='0'&&c<='9'){date=date*10+c-'0';c=getchar();}
return date*w;
}
void work(){
dp[0]=10;
for(int i=1;i<=n;i++)
for(int j=m;j>=0;j--)
if(dp[j]>=a[i].t){
if(j+a[i].h>=m){
printf("%d\n",a[i].t);
return;
}
dp[j+a[i].h]=max(dp[j],dp[j+a[i].h]);
dp[j]+=a[i].f;
}
printf("%d\n",dp[0]);
}
void init(){
m=read();n=read();
for(int i=1;i<=n;i++){a[i].t=read();a[i].f=read();a[i].h=read();}
sort(a+1,a+n+1);
memset(dp,-1,sizeof(dp));
}
int main(){
init();
work();
return 0;
}
```