P1941 NOIP2014 提高组 飞扬的小鸟 题解

P1941 NOIP2014 提高组 飞扬的小鸟

分析

背包经典演变问题玩得挺花。

设 \(f[i][j]\) 表示 到达 \((i, j)\) 的时候的最小点击次数。题目中对于每一个 \(i\) 有两种处理：点击与不点击（重点：点击可以叠加）。所以，对于点击，我们可以像完全背包一样转移，而不点击就按照 01 背包转移。

对于管道，我们把管道的 \(f[i][j]\) 设为 \(\inf\) 表示无法到达。

点击之后高度可能超过 \(m\)，但是题目说了最高到 \(m\)，所以超过 \(m\) 的一律当在 \(m\) 高度处理。

代码里有详细说明。

代码 | 解析

// Momoka!!!
#include <bits/stdc++.h>
using namespace std;

const int maxn = 10005;
const int maxm = 2005;
int n, m, k;
int up[maxn], down[maxn];
int low[maxn], high[maxn];
// f[i][j]：到达 (i, j) 时的最小点击次数。
int f[maxn][maxm]; // 可选择点击与不点击，点击可以叠加；点击按照完全背包转移，不点击按照 01 背包转移。
bool isPipe[maxn];

int main() {
	scanf("%d%d%d", &n, &m, &k);
	for (int i = 1; i <= n; i++) {
		scanf("%d%d", &up[i], &down[i]);
	}
	for (int i = 1; i <= k; i++) {
		int p, l, h;
		scanf("%d%d%d", &p, &l, &h);
		isPipe[p] = true, low[p] = l, high[p] = h;
	}
	memset(f, 0x3f, sizeof(f));
	for (int i = 1; i <= m; i++) f[0][i] = 0;
	for (int i = 1; i <= n; i++) {
		// 向上（点击）按照完全背包转移。
		for (int j = up[i] + 1; j <= m + up[i]; j++) {
			f[i][j] = min(f[i - 1][j - up[i]] + 1, f[i][j - up[i]] + 1);
		}
		// 点击之后向上飞可能超过 m，但是题目说了最高飞到 m，可以一直贴着最顶上飞。
		for (int j = m + 1; j <= m + up[i]; j++) {
			f[i][m] = min(f[i][j], f[i][m]); // 所以处理一下。
		}
		// 向下（不点击）按照 01 背包转移
		for (int j = 1; j <= m - down[i]; j++) {
			// 为什么 01 背包不从大到小枚举？
			// 因为用 f[i-1][j+down[i]] 来转移，所以从 1 到 m-down[i] 才是 01 背包。
			f[i][j] = min(f[i][j], f[i - 1][j + down[i]]);
		}
		// 刚才把 i 列当作没有管道（障碍）了，若 i 列是管道，则需要消除影响。
		if (isPipe[i]) {
			for (int j = 1; j <= low[i]; j++) {
				f[i][j] = 0x3f3f3f3f;
			}
			for (int j = high[i]; j <= m; j++) {
				f[i][j] = 0x3f3f3f3f;
			}
		}
	}
	int ans = 0x3f3f3f3f;
	for (int i = 1; i <= m; i++) {
		ans = min(ans, f[n][i]);
	}
	if (ans < 0x3f3f3f3f) {
		printf("1\n%d", ans);
	} else {
		// 无法完成游戏。
		ans = 0;
		bool flag = true;
		int endpos = 0;
		for (int i = n; i >= 1; i--) {
			for (int j = 1; j <= m; j++) {
				if (f[i][j] < 0x3f3f3f3f) {
					flag = false;
					endpos = i; // 最后可以到达的地方。
					break;
				}
			}
			if (!flag) break;
		}
		// 统计所有经过的管道。
		for (int i = 1; i <= endpos; i++) {
			if (isPipe[i]) ans++;
		}
		printf("0\n%d", ans);
	}
	return 0;
}