洛谷 P1156 垃圾陷阱

原题链接

Solution

算法：背包

看似毫无关系，下面我们来分析一下。

把深度 \(D\) 看作背包容量，每个垃圾堆放高度 \(h\) 看作物体体积，增加生命长度 \(l\) 看作物体价值。

这不就是一个背包了嘛。

定义 \(f[i][j]\) 表示到第 \(i\) 个垃圾，高度为 \(j\) 时拥有的最长生命时间。

转移方程

第 \(i\) 个垃圾用于增加生命：\(f[i][j] = max(f[i][j], f[i - 1][j] + a[i].l - (a[i].t - a[i - 1].t)\)

第 \(i\) 个垃圾用于搭高： \(f[i][j] = max(f[i][j], f[i - 1][j - a[i].h] - (a[i].t - a[i - 1].t)\)

这个 \(f\) 第一维也是可以用滚动数组消掉的。

看代码理解吧

完整代码

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>

using namespace std;

const int N = 1010;
struct node{
	int t, l, h;
}a[N];
int m, n;
int f[2][N];		//前i个垃圾，到高度j拥有的最长生命时间（滚动）

bool cmp(node x, node y){
	return x.t < y.t;
}

int main(){
	scanf("%d%d", &m, &n);
	for(int i = 1; i <= n; i++)
		scanf("%d%d%d", &a[i].t, &a[i].l, &a[i].h);
	sort(a + 1, a + 1 + n, cmp);
	f[0][0] = 10;
	int ans = 10;									//注意初值等于10
	for(int i = 1; i <= n; i++){
		int lin = i & 1, pre = lin ^ 1;				//滚动，自己理解一下
		memset(f[lin], 128, sizeof(f[lin]));		//注意要不停的赋初始值
		for(int j = m; j >= 0; j--){
			if(f[pre][j] < a[i].t - a[i - 1].t) continue;
			if(j + a[i].h >= m){					//高度>=m 就输出
				printf("%d\n", a[i].t);
				return 0;
			}
			f[lin][j + a[i].h] = max(f[lin][j + a[i].h], f[pre][j] - (a[i].t - a[i - 1].t));	//转移
			f[lin][j] = max(f[lin][j], f[pre][j] + a[i].l - (a[i].t - a[i - 1].t));
		}
		ans = max(ans, f[lin][0] + a[i].t);			//不能出去的话，最长生命长度（高度为0）
	}
	printf("%d\n", ans);
	return 0;
}

End