题目链接
给定 $n*m$ 的游戏界面，求是否可以通过操作使小鸟通过所有管道以及最少操作次数。
$n\le 10000,m\le 1000$
这篇博客不会在洛谷发表，所以内容可能比较放飞自我。
神仙shiwt巨佬早在去年的这个时候就已经切掉了这个神仙题。
记 $f[i][j]$ 表示从起点飞到坐标 $(i,j)$ 所需的最小步数。考虑 $f[i][j]$ 的转移。它要么是从 $(i-1,j+Y)$ 那里掉下来的，也有可能是从 $(i-1,j-kX)$ 那里升上来的。
考虑优化。 $(i-1,j-kX)$ 的枚举较为啰嗦；不难发现如果小鸟🐦可以飞到 $(i,j-X)$ ，那么它再飞一下不就到 $(i,j)$ 了吗？
状态转移方程如下：
$$
f[i][j]=\min {f[i-1][j+Y],f[i][j-X]+1,f[i-1][j-X]+1}
$$
不妨写个滚动数组。
代码如下：
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
48
49
50
51
52
53
| #include <bits/stdc++.h>
using namespace std;
const int MAXN = 10005;
const int MAXM = 1005;
const int INF = 0x3f3f3f3f;
int N, M, K;
int X[MAXN], Y[MAXN];
int L[MAXN], R[MAXN];
int f[2][MAXM * 2];
int cnt, minn;
int main() {
scanf("%d%d%d", &N, &M, &K);
for (register int i = 1; i <= N; ++i)
scanf("%d%d", &X[i], &Y[i]);
for (register int i = 1; i <= K; ++i) {
int p, l, h;
scanf("%d%d%d", &p, &l, &h);
L[p] = l, R[p] = h;
}
for (register int i = 1; i <= N; ++i) {
int cur = i & 1;
minn = INF;
for (register int j = 0; j <= M + X[i]; ++j)
f[cur][j] = INF;
for (register int j = X[i]; j <= M + X[i]; ++j)
f[cur][j] = min(f[cur][j], min(f[cur ^ 1][j - X[i]] + 1, f[cur][j - X[i]] + 1));
for (register int j = M + 1; j <= M + X[i]; ++j)
f[cur][M] = min(f[cur][M], f[cur][j]);
for (register int j = 0; j <= M - Y[i]; ++j)
f[cur][j] = min(f[cur][j], f[cur ^ 1][j + Y[i]]);
if (L[i] || R[i]) {
for (register int j = 0; j <= L[i]; ++j)
f[cur][j] = INF;
for (register int j = R[i]; j <= M; ++j)
f[cur][j] = INF;
}
f[cur][0] = INF;
for (register int j = 0; j <= M; ++j)
minn = min(minn, f[cur][j]);
if (minn == INF) {
puts("0");
printf("%d", cnt);
return 0;
}
cnt += L[i] || R[i];
}
puts("1");
printf("%d", minn);
return 0;
}
|