P1156 垃圾陷阱

1.题解

首先该题是一个线性dp问题 由于贪心的考虑我们每次到当前时间有可以取的垃圾都会直接捡起而不会再过一会儿 所以我们可以把每一个出现时间作为策略点 这样从头开始dp 所以我们首先需要对a数组进行排序

排序以后就可以从第一个垃圾到最后一个垃圾来dp了 那dp方程如何设计呢 我们考虑假如当前有更多的生命的话那么后续选择也有更多的余地 所以我们可以设$f[i][j]$表示当前考虑到第$i$个物品且在$j$高度时生命值最大是多少

然后和背包问题一样的分析方法

需要注意的是这里由背包的取或不取变成了是堆还是吃 所以我们的$i$一定是从$i-1$推过来的 那我们现在考虑$f[i-1][j]$假如此时这个状态的生命值小于$t_i-t_{i-1}$那么就不能递推过来 所以只需要考虑$f[i-1][j]>=t_i-t_{i-1}$ 需要注意的是可能出现一些时间相同的垃圾 所以有可能差值为0 那么假如我们初始化f为0就可能会更新一些莫名其妙的没有意义的状态然后就WA了 所以我们先给f初始化一个负数

现在$i-1$可以转移到$i$了 那么

  1. 第$i$个物品用来吃

那么$f[i][j]=max(f[i][j],f[i-1][j]-(t_i-t_{i-1})+w_i)$

注意我们用$w$来表示这个垃圾能提供的生命值

这个方程还是比较好懂的 我们$f[i][j]$从$f[i-1][j]$推过来 首先需要花费$t_i-t_{i-1}$的生命值 然后吃了$i$以后又加了$w_i$的生命值

2.第$i$个物品用来堆

那么我们$f[i-1][j]$就可以更新到$f[i][j+h_i]$注意假如这时候高度$j+h_i$大于等于d就已经可以了 直接输出到第$i$个点的时间即可

假如还是在范围内的话就有

$f[i][j+h_i]=max(f[i][j+h_i],f[i-1][j]-(t_i-t_{i-1}))$ 这个式子与上面那个差不多 就是从$i-1$转移到$i$ 此时花费了$t_i-t_{i-1}$然后高度由$j$变成了$j+h_i$

假如$n$个物品考虑完了还没有找到跳出去的办法那他就被困在井里了 这时候我们需要输出它最多存活多久 这个可以直接算出来 每次遇到物品就把当前生命加上它的贡献 假如生命值已经够不到第$i$个物品出现的时间了 就输出当前时间好了 这就是个简单的贪心

2.AC代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=250;
int f[maxn][maxn];
int n,m;
struct node{
	int t,h,f;
	bool operator<(const node&p)
	{
		if(t==p.t) return t<p.t;
	}
}a[maxn];
int main()
{
	cin>>m>>n;
	for(int i=1;i<=n;i++) cin>>a[i].t>>a[i].f>>a[i].h;
	sort(a+1,a+n+1);
	memset(f,-1,sizeof(f));
	f[0][0]=10;
	for(int i=1;i<=n;i++)
	{
		for(int j=0;j<m;j++)
		{
			if(f[i-1][j]>=a[i].t-a[i-1].t)
			{
				if(j+a[i].h>=m) 
				{
					cout<<a[i].t<<endl;
					return 0;
				}
				f[i][j+a[i].h]=max(f[i][j+a[i].h],f[i-1][j]-a[i].t+a[i-1].t);
				f[i][j]=max(f[i][j],f[i-1][j]-a[i].t+a[i-1].t+a[i].f);
			}
		}
	}
	int ans=10;
	for(int i=1;i<=n;i++)
	{
		if(ans<a[i].t) break;
		ans+=a[i].f;
	}
	cout<<ans<<endl;
	return 0;
}