Luogu-P1941

题面

题目大意是要玩一个类似Flappy Bird的游戏,输入会给出地图以及每个x坐标对应的数据。小鸟每秒前进一格,可以在1s内连续点很多下让小鸟上升,也可以不点让他下降,对于每个不同的横坐标x上升和下降的值都不同,问你最少点多少下能让小鸟到达终点,如果到不了终点那么最远可以走多远。(具体题目看题面吧)

也就是说,在每个点我们都有两种选择:点k下使得可以到达下一格,或者不点让小鸟下降。

我们记状态转移函数为 $F(i, j)$ 其中 $i$ 为当前到达的格子(横坐标),$j$ 为当前的高度,函数的值代表对于$i, j$需要点击的最小次数

很显然嘛在每个点如果选择上升就相当于是完全背包(因为可以上升任意次)

1
for (int j = up[i - 1] + 1; j <= M + up[i - 1]; ++j) {
2
	F[i][j] = min(F[i][j - up[i - 1]] + 1, F[i - 1][j - up[i - 1]] + 1);
3
}

对于下降则是01背包(只能下降一次)。

1
for (int j = 1; j <= M - down[i - 1]; ++j) {
2
	F[i][j] = min(F[i][j], F[i - 1][j + down[i - 1]]);
3
}

但是这题有个恶心的点在于,如果小鸟上升后高度超过了最高点,那么其高度仍然在最高点(你永远超过不了最高点)所以对于最高点需要特殊处理
(我们把高度上限设置为原来的两倍,然后对于每个超出最大高度的点单独处理)

1
for (int j = M + 1; j <= M + up[i - 1]; ++j) {
2
	F[i][M] = min(F[i][M], F[i][j]);
3
}

对于无法到达的点,则将其值设为无穷

AC代码

1
#include <iostream>
2
#include <algorithm>
3
4
using namespace std;
5
6
const int Inf = 0x3f3f3f3f;
7
const int maxn = 10015;
8
const int maxm = 1015 * 2;
9
const int maxk = maxn;
10
int up[maxn];
11
int down[maxn];
12
int ls[maxn];
13
int hs[maxn];
14
int _id[maxn];
15
int F[maxn][maxm];
16
17
auto main() -> int {
18
	ios::sync_with_stdio(false);
19
	cin.tie(nullptr);
20
	cout.tie(nullptr);
21
	int N, M, K;
22
	cin >> N >> M >> K;
23
	fill(ls, ls + maxn, 1);
24
	fill(hs, hs + maxn, M + 1);
25
	for (int i = 0; i < N; ++i) {
26
		cin >> up[i] >> down[i];
27
	}
28
	for (int i = 0; i < K; ++i) {
29
		int p;
30
		cin >> p;
31
		cin >> ls[p] >> hs[p];
32
		ls[p]++;
33
		hs[p]--;
34
		_id[p] = 1;
35
	}
36
	for (int i = 0; i <= N; ++i) {
37
		if(_id[i] == 0) _id[i] = _id[i - 1];
38
		else _id[i] = _id[i - 1] + 1;
39
	}
40
	F[0][0] = Inf;
41
	fill(F[0] + 1, F[0] + maxm, 0);
42
	for (int i = 1; i <= N; ++i) {
43
		fill(F[i], F[i] + maxm, Inf);
44
	}
45
	for (int i = 1; i <= N; ++i) {
46
		for (int j = up[i - 1] + 1; j <= M + up[i - 1]; ++j) {
47
			F[i][j] = min(F[i][j - up[i - 1]] + 1, F[i - 1][j - up[i - 1]] + 1);
48
		}
49
		for (int j = M + 1; j <= M + up[i - 1]; ++j) {
50
			F[i][M] = min(F[i][M], F[i][j]);
51
		}
52
		for (int j = 1; j <= M - down[i - 1]; ++j) {
53
			F[i][j] = min(F[i][j], F[i - 1][j + down[i - 1]]);
54
		}
55
		for (int j = 0; j < ls[i]; ++j) {
56
			F[i][j] = Inf;
57
		}
58
		for (int j = hs[i] + 1; j <= M; ++j) {
59
			F[i][j] = Inf;
60
		}
61
	}
62
	int ans = Inf;
63
	for (int i = N; i >= 0; --i) {
64
		for (int j = 1; j <= M; ++j) {
65
			ans = min(ans, F[i][j]);
66
			if(N != i && ans != Inf) {
67
				cout << 0 << endl;
68
				cout << _id[i] << endl;
69
				return 0;
70
			}
71
		}
72
		if(i == N && ans != Inf) {
73
			cout << 1 << endl;
74
			cout << ans << endl;
75
			return 0;
76
		}
77
	}
78
	return 0;
79
}