[NOIP 2014 提高组] 飞扬的小鸟

GitHub 跳转原题关系图返回列表

用按高度滚动的动态规划合并连续点击与重力转移，并在管道位置过滤非法高度。

OJ: luogu

题目 ID: P1941

难度:普及+/提高

标签:动态规划DP模拟

日期: 2026-07-24 17:47

前置题目

luogu P7074[CSP-J 2020] 方格取数网格列间 DP + 列内纵向转移的基本模型。

相似题目

luogu P7074[CSP-J 2020] 方格取数同是列间递推+列内纵向转移模型，P1941 更复杂（跳跃+重力+障碍）。

题意

小鸟从横坐标 0 的任意高度出发，每个单位时间向右移动一格。点击可以上升 x[i]，同一时间可以点击多次；不点击则下降 y[i]。高度超过 m 时停在 m，高度为 0 或碰到管道边界则失败。

如果能到达横坐标 n，求最少点击次数；否则求最多通过的管道数量。

思路

先看一个直接枚举每一步操作的朴素解：

cpp

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
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-07-24 17:47
 * update_at: 2026-07-24 17:53
 */
// brute.cpp：小数据暴力解，用来帮助理解题意并辅助对拍。
#include <bits/stdc++.h>
using namespace std;

const int INF = 1000000000;
const int MAXN = 20;

int n, m, k;
int up_step[MAXN], down_step[MAXN];
int has_pipe[MAXN], pipe_low[MAXN], pipe_high[MAXN];
int best_clicks = INF;
int most_passed = 0;

void search_paths(int position, int height, int clicks, int passed_pipes) {
    most_passed = max(most_passed, passed_pipes);
    if (position == n) {
        best_clicks = min(best_clicks, clicks);
        return;
    }

    int rise = up_step[position];
    // 枚举这一步点击 1 次、2 次……，直到高度达到 m。
    // 到达 m 后再点击一次仍会停在 m，这也是一次合法的时间转移。
    int target = height;
    for (int count = 1;; count++) {
        target = min(m, target + rise);
        int next_position = position + 1;
        if (!has_pipe[next_position]
            || (target > pipe_low[next_position] && target < pipe_high[next_position])) {
            search_paths(next_position, target, clicks + count, passed_pipes + has_pipe[next_position]);
        }
        if (target == m) {
            break;
        }
    }

    // 枚举这一步不点击的情况。
    target = height - down_step[position];
    if (target > 0) {
        int next_position = position + 1;
        if (!has_pipe[next_position]
            || (target > pipe_low[next_position] && target < pipe_high[next_position])) {
            search_paths(next_position, target, clicks, passed_pipes + has_pipe[next_position]);
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m >> k;
    for (int position = 0; position < n; position++) {
        cin >> up_step[position] >> down_step[position];
    }
    for (int i = 1; i <= k; i++) {
        int position, low, high;
        cin >> position >> low >> high;
        has_pipe[position] = 1;
        pipe_low[position] = low;
        pipe_high[position] = high;
    }

    // 小数据从每个合法初始高度出发，完整枚举每一步的点击次数。
    for (int height = 1; height <= m; height++) {
        search_paths(0, height, 0, 0);
    }

    if (best_clicks < INF) {
        cout << 1 << '\n' << best_clicks << '\n';
    } else {
        cout << 0 << '\n' << most_passed << '\n';
    }
    return 0;
}

这个暴力把每次点击次数和不点击都枚举出来，只适合小数据。优化时定义 dp[h] 为到达当前列高度 h 的最少点击次数。一次点击先转移到 min(m,h+x)，再在当前数组中从低到高补齐连续点击；目标高度为 m 时，m-x 到 m-1 的来源都要纳入。另一条转移是不点击，从旧高度 h+y 到新高度 h，代价不变。

到达管道位置后只保留 l<height<h 的状态。若没有状态，说明当前管道无法通过；否则增加已经通过的管道计数。

DP 状态表

下面的表展示抓取样例前两次移动中，上一列状态、上升转移、下降转移和合并结果。单元格是到达对应高度的最少点击次数，∞ 表示不可达。

状态	h=1	h=2	h=3	h=4	h=5	h=6	h=7	h=8	h=9	h=10
位置 0 前的 dp	0	0	0	0	0	0	0	0	0	0
位置 1：上升（含连续点击）	∞	∞	∞	1	1	1	1	1	1	1
位置 1：下降（不点击）	0	∞	∞	∞	∞	∞	∞	∞	∞	∞
位置 1：合并后 dp	0	∞	∞	1	1	1	1	1	1	1
位置 1 前的 dp	0	∞	∞	1	1	1	1	1	1	1
位置 2：上升（含连续点击）	∞	∞	∞	∞	∞	∞	∞	∞	∞	1
位置 2：下降（不点击）	1	∞	∞	∞	∞	∞	∞	∞	∞	∞
位置 2：合并后 dp	1	∞	∞	∞	∞	∞	∞	∞	∞	1

第一步的 x=3,y=9，所以点击结果从高度 4 开始可达，下降结果只有从 10 降到 1。第二步的 x=9 会把多种来源都封顶到 10，这正是代码单独处理 next_dp[m] 的原因。

代码

cpp

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
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-07-24 17:47
 * update_at: 2026-07-24 17:51
 */
#include <bits/stdc++.h>
using namespace std;

const int INF = 1000000000;
const int MAXN = 10005;
const int MAXM = 1005;

int n, m, k;
int up_step[MAXN], down_step[MAXN];
int has_pipe[MAXN], pipe_low[MAXN], pipe_high[MAXN];
int dp[MAXM], next_dp[MAXM];

bool has_reachable_height() {
    for (int height = 1; height <= m; height++) {
        if (dp[height] < INF) {
            return true;
        }
    }
    return false;
}

int minimum_clicks() {
    for (int height = 1; height <= m; height++) {
        dp[height] = 0;
    }

    int passed_pipes = 0;
    for (int position = 1; position <= n; position++) {
        for (int height = 1; height <= m; height++) {
            next_dp[height] = INF;
        }

        int rise = up_step[position - 1];
        int fall = down_step[position - 1];

        // 点击一次到达 min(m, height + rise)，再用下面的循环补齐连续点击。
        for (int height = 1; height <= m; height++) {
            if (dp[height] >= INF) {
                continue;
            }
            int target = min(m, height + rise);
            next_dp[target] = min(next_dp[target], dp[height] + 1);
        }

        // 对于还没有到顶的高度，每增加 rise 高度需要再点击一次。
        for (int height = rise + 1; height < m; height++) {
            if (next_dp[height - rise] < INF) {
                next_dp[height] = min(next_dp[height], next_dp[height - rise] + 1);
            }
        }

        // 到达 m 时会封顶，所以 m-rise 到 m-1 的状态都能一步到达 m。
        int source_begin = max(1, m - rise);
        for (int height = source_begin; height < m; height++) {
            if (next_dp[height] < INF) {
                next_dp[m] = min(next_dp[m], next_dp[height] + 1);
            }
        }

        // 不点击时下降 fall，高度不能降到 0。
        for (int height = fall + 1; height <= m; height++) {
            if (dp[height] < INF) {
                next_dp[height - fall] = min(next_dp[height - fall], dp[height]);
            }
        }

        for (int height = 1; height <= m; height++) {
            dp[height] = next_dp[height];
        }

        if (has_pipe[position]) {
            for (int height = 1; height <= m; height++) {
                if (height <= pipe_low[position] || height >= pipe_high[position]) {
                    dp[height] = INF;
                }
            }
            if (!has_reachable_height()) {
                cout << 0 << '\n' << passed_pipes << '\n';
                return -1;
            }
            passed_pipes++;
        } else if (!has_reachable_height()) {
            cout << 0 << '\n' << passed_pipes << '\n';
            return -1;
        }
    }

    int answer = INF;
    for (int height = 1; height <= m; height++) {
        answer = min(answer, dp[height]);
    }
    cout << 1 << '\n' << answer << '\n';
    return answer;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m >> k;
    for (int position = 0; position < n; position++) {
        cin >> up_step[position] >> down_step[position];
    }
    for (int i = 1; i <= k; i++) {
        int position, low, high;
        cin >> position >> low >> high;
        has_pipe[position] = 1;
        pipe_low[position] = low;
        pipe_high[position] = high;
    }

    minimum_clicks();
    return 0;
}

复杂度

时间复杂度：O(nm)。
空间复杂度：O(n+m)。

总结

这道题的核心是把完整飞行路线压缩成“当前位置 + 高度”的最优状态。连续点击可以在同一层用递推展开，重力是不点击的反向高度转移，管道则只是对状态集合做过滤。

P1941 [NOIP 2014 提高组] 飞扬的小鸟

题目背景

NOIP2014 提高组 D1T3

题目描述

Flappy Bird 是一款风靡一时的休闲手机游戏。玩家需要不断控制点击手机屏幕的频率来调节小鸟的飞行高度，让小鸟顺利通过画面右方的管道缝隙。如果小鸟一不小心撞到了水管或者掉在地上的话，便宣告失败。

为了简化问题，我们对游戏规则进行了简化和改编:

游戏界面是一个长为 $n$ ，高为 $m$ 的二维平面，其中有 $k$ 个管道（忽略管道的宽度）。

小鸟始终在游戏界面内移动。小鸟从游戏界面最左边任意整数高度位置出发，到达游戏界面最右边时，游戏完成。

小鸟每个单位时间沿横坐标方向右移的距离为 $1$ ，竖直移动的距离由玩家控制。如果点击屏幕，小鸟就会上升一定高度 $x$ ，每个单位时间可以点击多次，效果叠加；如果不点击屏幕，小鸟就会下降一定高度 $y$ 。小鸟位于横坐标方向不同位置时，上升的高度 $x$ 和下降的高度 $y$ 可能互不相同。

小鸟高度等于 $0$ 或者小鸟碰到管道时，游戏失败。小鸟高度为 $m$ 时，无法再上升。

现在，请你判断是否可以完成游戏。如果可以，输出最少点击屏幕数；否则，输出小鸟最多可以通过多少个管道缝隙。

输入格式

第 $1$ 行有 $3$ 个整数 $n, m, k$ ，分别表示游戏界面的长度，高度和水管的数量，每两个整数之间用一个空格隔开。

接下来的 $n$ 行，每行 $2$ 个用一个空格隔开的整数 $x$ 和 $y$ ，依次表示在横坐标位置 $0 \sim n-1$ 上玩家点击屏幕后，小鸟在下一位置上升的高度 $x$ ，以及在这个位置上玩家不点击屏幕时，小鸟在下一位置下降的高度 $y$ 。

接下来 $k$ 行，每行 $3$ 个整数 $p,l,h$ ，每两个整数之间用一个空格隔开。每行表示一个管道，其中 $p$ 表示管道的横坐标， $l$ 表示此管道缝隙的下边沿高度， $h$ 表示管道缝隙上边沿的高度（输入数据保证 $p$ 各不相同，但不保证按照大小顺序给出）。

输出格式

共两行。

第一行，包含一个整数，如果可以成功完成游戏，则输出 $1$ ，否则输出 $0$ 。

第二行，包含一个整数，如果第一行为 $1$ ，则输出成功完成游戏需要最少点击屏幕数，否则，输出小鸟最多可以通过多少个管道缝隙。

输入输出样例 #1

输入 #1

text

输出 #1

text

1
21
6

输入输出样例 #2

输入 #2

text

输出 #2

text

1
20
3

说明/提示

【输入输出样例说明】

如下图所示，蓝色直线表示小鸟的飞行轨迹，红色直线表示管道。

【数据范围】

对于 $30\%$ 的数据： $5 \leq n \leq 10, 5 \leq m \leq 10, k=0$ ，保证存在一组最优解使得同一单位时间最多点击屏幕 $3$ 次；

对于 $50\%$ 的数据： $5 \leq n \leq 20, 5 \leq m \leq 10$ ，保证存在一组最优解使得同一单位时间最多点击屏幕 $3$ 次；

对于 $70\%$ 的数据： $5 \leq n \leq 1000, 5 \leq m \leq 100$ ；

对于 $100\%$ 的数据： $5 \leq n \leq 10000$ ， $5 \leq m \leq 1000$ ， $0 \leq k < n$ ， $0 < x,y < m$ ， $0 < p < n$ ， $0 \leq l < h \leq m$ ， $l + 1 < h$ 。

[NOIP 2014 提高组] 飞扬的小鸟

目录

题意

思路

DP 状态表

代码

复杂度

总结