[NOIP2014]飞扬的小鸟

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

按横坐标滚动的一维 DP：上升用完全背包式链式递推把任意次点击压成一次升序扫描，下降与管道过滤用切片，同一趟同时维护最少点击和最多过管两个目标。

OJ: roj

题目 ID: 3620

难度:普及+/提高-

标签:动态规划DPpython

创建: 2026-10-02 10:54

更新: 2026-10-10 11:30

目录

  1. 形式化题目
  2. 正解
    1. 思路
    2. 代码
    3. 复杂度
  3. 总结
  4. 图示解析

形式化题目

给定长 nn（横坐标 0∼n−10 \sim n-1）、高 mm 的平面：

  • 每个横坐标 xx 配一个上升量 X[x]X[x] 与下降量 Y[x]Y[x]，且 0<X[x],Y[x]<m0 < X[x], Y[x] < m；
  • kk 根管道位于横坐标 PP（互不相同、不保证有序），缝隙是开区间 (L,H)(L, H)，满足 L+1<HL + 1 < H，即缝隙里至少留有一个整数高度；0<P<n0 < P < n，首列没有管道。

小鸟从 x=0x=0 的任意整数高度 h∈[1,m]h \in [1, m] 出发，每个单位时间右移 1 格；在这一个单位时间里，点击 t⩾1t \geqslant 1 次（效果叠加）则

h′=min⁡(m, h+t X[x]), h' = \min(m,\ h + t\,X[x]),

一次也不点则 h′=h−Y[x]h' = h - Y[x]。 高度变成 00、或高度落在管道上（h⩽Lh \leqslant L 或 h⩾Hh \geqslant H）即失败；走完 nn 步（抵达 x=nx=n）即通关。要求：能通关输出 11 和最少点击数，否则输出 00 和一条路径上最多通过的管道缝隙数。

样例 1（n=10, m=10n=10,\ m=10，管道在 x=1,5,6,7,8,9x=1,5,6,7,8,9）输出 1 / 6。一条最优路线从高度 11 出发：点 1 次升到 44（过缝隙 (2,7)(2,7)）→ 点 1 次到顶 min⁡(10,13)=10\min(10,13)=10 → 不点降到 88、55、33（过缝隙 (1,5)(1,5)）→ 点 1 次到 44（过 (3,5)(3,5)）→ 点 1 次到 66（过 (5,8)(5,8)）→ 点 1 次到 88（过 (7,9)(7,9)）→ 不点降到 22（过 (1,3)(1,3)）→ 点 1 次到 44 抵达右端。共点击 66 次，66 根管道全部通过。

样例 2（管道在 x=1,3,6,9x=1,3,6,9）输出 0 / 3。起点高度 33 不点降到 11 可过第一条缝隙 (0,2)(0,2)（高度 22 贴上边沿即撞管），随后升到 99 过缝隙 (8,10)(8,10)、降到 88 过缝隙 (7,9)(7,9)。但所有路线到 x=8x=8 时只剩高度 6,9,106,9,10，再走一步只能到 {4,7,8,10}\{4,7,8,10\}，没有一个落在缝隙 (1,4)(1,4) 内，于是 x=9x=9 处全部撞管：游戏必败，最多通过前 33 根管道。

正解

思路

朴素做法与瓶颈。 把每个 (横坐标, 高度) 当状态做搜索或 DP 是自然的，但转移要枚举"这一格点几次"：t=1,2,…t = 1, 2, \dots 直到被 mm 封顶，单个状态约有 m/X[x]m / X[x] 个候选，总复杂度 O ⁣(n⋅m⋅m/X[x])O\!\left(n \cdot m \cdot m / X[x]\right)，X[x]=1X[x]=1、m=1000m=1000 时达到 101010^{10}。浪费在于：这些候选彼此只差"多点一次"，逐个枚举其实是在重复计算同一条链上的前缀。

状态与转移。 设 tap[h] 是当前列高度 hh 的最少点击数（不可达为 ∞\infty），cnt[h] 是对应路径的最多过管数（不可达为 −1-1）。每次右移一格，候选转移只有三类：

转移 条件 落点 tap（取 min⁡\min） cnt（取 max⁡\max）
点 t⩾1t \geqslant 1 次 来源可达 min⁡(m, h+t X[x])\min(m,\ h + t\,X[x]) 纳入来源 + t+\,t 纳入来源
一次不点 来源可达且 h>Y[x]h > Y[x] h−Y[x]h - Y[x] 纳入来源 纳入来源
过管道（抵达 xx 时） 该列有缝隙 (L,H)(L, H) 高度不变 不变 缝隙外整段置为不可达；缝隙内 +1+1

表中前两行是水平移动产生的候选，第三行是到达新列后的过滤；三行对 tap / cnt 的更新形式完全同构（一个取 min⁡\min、一个取 max⁡\max），这正是两个目标能同趟算完的原因。每列也按固定顺序执行：上升链 → 下降切片 → 对下一列的管道过滤，顺序错了链就会混入下降值（见下）。

关键观察：点 tt 次是一条链。 从 hh 连点 tt 次到达 min⁡(m,h+t X[x])\min(m, h + t\,X[x])、代价 +t+t，等价于在"步长 X[x]X[x]"上反复走一步：h→h+X[x]h \to h+X[x] 每步代价 +1+1。于是不必枚举 tt——固定一列，按高度升序扫描，先把"上一层点一次"写进 f′f'，再用本轮已更新的 f′[h]+1f'[h] + 1 写 f′[min⁡(m,h+X)]f'[\min(m, h+X)]（正文的 f′f' 即代码里的 nxt_tap / nxt_cnt）。轮到下标 hh 时 f′[h]f'[h] 已经收齐所有来源（能写它的下标只有 h−X<hh - X < h），所以这一式恰好覆盖所有 tt；这正是完全背包的正序更新。扫描期间 f′f' 里只有上升结果，链不会混进"下降"产生的值——因此必须先做上升链、再做下降。

下降与管道都用切片。 下降只有单一候选：落点 1∼m−Y1 \sim m{-}Y 对应起点 Y+1∼mY{+}1 \sim m，整段切片逐元素比较即可，且落进地面（落点 <1<1）的起点天然不在切片里。管道过滤同理：把 1∼L1 \sim L 与 H∼mH \sim m 两段整体置为不可达，缝隙 (L,H)(L, H) 内的存活状态计数 +1+1——"贴边即撞管"和"过管计数"在同一个切片里完成，不需要额外的存活标记。

两个目标同趟完成。 边能不能走只取决于状态是否可达，与两个聚合值无关；点击用 min⁡\min 聚合、计数用 max⁡\max 聚合，各自只读上一列的自己。因此每个状态同时携带两个值、一趟转移同时更新，等价于跑两遍 DP。由于路径可能中途坠毁，失败答案 cnt 的最大值必须逐列维护，不能只看最后一列。

样例 1 前两列的 DP 快照（X[0]=3, Y[0]=9X[0]=3,\ Y[0]=9；x=1x=1 处缝隙为 (2,7)(2,7)），展示转移结果与管道过滤：

高度 hh x=0x=0 出发 tap x=1x=1 转移后 tap x=1x=1 过管道后 tap 过管计数 cnt
11 00 00（由高度 1010 不点下落） ∞\infty（h⩽Lh \leqslant L 撞下边沿） —
22 00 ∞\infty ∞\infty（贴下边沿） —
33 00 ∞\infty ∞\infty（缝隙内但不可达） —
44 00 11 11 11
55 00 11 11 11
66 00 11 11 11
77 00 11 ∞\infty（贴上边沿 H=7H=7） —
88 00 11 ∞\infty（缝隙上方） —
99 00 11 ∞\infty（缝隙上方） —
1010 00 11 ∞\infty（缝隙上方） —

表中 tap 为最少点击数，∞\infty 表示不可达，— 表示已撞管。出发时任意高度代价都是 00；一格之内点 1 次可以到达 4∼104 \sim 10（高度 11 点一次升到 44，高度 ⩾7\geqslant 7 点一次被顶到 1010），不点只有高度 1010 能落到 11。过滤后只剩 4,5,64,5,6 存活并各记 11 次点击、通过 11 根管道——高度 1,21,2 低于下边沿、77 贴上边沿、8∼108 \sim 10 在缝隙上方，全部撞管。

正确性要点。 用归纳法：处理完第 xx 列的过滤后，两个数组恰是"存活到达该列各高度"的最优值，且不可达状态两哨兵成对出现。基础是第 00 列全 00；递推步中 rise 枚举完"点 t⩾1t \geqslant 1 次"的全部落点并取 min⁡/max⁡\min/\max，fall 枚举完"不点"的唯一落点，pass_pipe 的切片精确删除缝隙外状态、给缝隙内 +1+1。终点无管道（P<nP < n），所以 tap 的最小值有限当且仅当可通关，且就是最少点击数。

代码

cpp
/**
 * 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-10-10 11:30
 * update_at: 2026-10-10 11:30
 */

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int INF=1000000000;
void rise(vector<int>&nt, vector<int>&nc, vector<int>&tap, vector<int>&cnt, int dx, int m){ for(int h=1;h<=m;h++){int t=h+dx; if(t>m) t=m; int v=tap[h]+1; if(v<nt[t]) nt[t]=v; if(cnt[h]>nc[t]) nc[t]=cnt[h]; int w=nt[h]+1; if(w<nt[t]) nt[t]=w; if(nc[h]>nc[t]) nc[t]=nc[h];}}
void fall(vector<int>&nt, vector<int>&nc, vector<int>&tap, vector<int>&cnt, int dy, int m){ for(int to=1;to<=m-dy;to++){int from=to+dy; if(tap[from]<nt[to]) nt[to]=tap[from]; if(cnt[from]>nc[to]) nc[to]=cnt[from];}}
void pass_pipe(vector<int>&nt, vector<int>&nc, pair<int,int> gap, int m){int low=gap.first, high=gap.second; for(int h=1;h<=low;h++){nt[h]=INF; nc[h]=-1;} for(int h=high;h<=m;h++){nt[h]=INF; nc[h]=-1;} for(int h=low+1;h<high;h++) if(nc[h]>=0) nc[h]++;}
int main(){ios::sync_with_stdio(false);cin.tie(nullptr); int n,m,k; if(!(cin>>n>>m>>k)) return 0; vector<pair<int,int> > steps(n); for(int i=0;i<n;i++) cin>>steps[i].first>>steps[i].second; vector<pair<int,int> > pipe(n, {-1,-1}); for(int i=0;i<k;i++){int p,l,h;cin>>p>>l>>h; pipe[p]={l,h};} vector<int> tap(m+1), cnt(m+1); int best=0; for(int x=0;x<n;x++){vector<int> nt(m+1,INF), nc(m+1,-1); rise(nt,nc,tap,cnt,steps[x].first,m); fall(nt,nc,tap,cnt,steps[x].second,m); if(x+1<n && pipe[x+1].first!=-1) pass_pipe(nt,nc,pipe[x+1],m); for(int h=1;h<=m;h++) best=max(best,nc[h]); tap=nt; cnt=nc;} int few=INF; for(int h=1;h<=m;h++) few=min(few,tap[h]); bool won=few<INF; cout<<(won?1:0)<<'\n'<<(won?few:best)<<'\n'; return 0;}
python
#!/usr/bin/env python3
# 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-10-02 10:54
# update_at: 2026-10-02 11:20

import sys

INF = 10**9   # 最少点击数的不可达哨兵：任一合法路径点击数不超过 n*m <= 1e7


def rise(nxt_tap: list[int], nxt_cnt: list[int], tap: list[int], cnt: list[int], dx: int, m: int) -> None:
    """上升转移：本单位时间至少点一次，多次点击效果叠加，到顶 m 封顶。

    按高度升序扫一遍即可传播"点 t 次"：写入 nxt_tap[t] 的是"从上一列点一次"，
    而 nxt_tap[h] 在轮到 h 时已经定型（只有下标 h-dx 会写它），所以
    `nxt_tap[h] + 1` 正是"同单位时间再叠一次"。此刻 nxt 里只有上升结果，
    链式叠加不会混入下降值。
    """
    for h in range(1, m + 1):
        t = h + dx
        if t > m:
            t = m                       # 到顶后再点也升不上去，统一收进 m
        v = tap[h] + 1                  # 上一列点一次到达 t
        if v < nxt_tap[t]:
            nxt_tap[t] = v
        if cnt[h] > nxt_cnt[t]:
            nxt_cnt[t] = cnt[h]
        w = nxt_tap[h] + 1              # 同一单位时间继续叠加点击
        if w < nxt_tap[t]:
            nxt_tap[t] = w
        if nxt_cnt[h] > nxt_cnt[t]:
            nxt_cnt[t] = nxt_cnt[h]


def fall(nxt_tap: list[int], nxt_cnt: list[int], tap: list[int], cnt: list[int], dy: int, m: int) -> None:
    """下降转移：一次也不点，整体下落 dy；落到 0 即坠毁，只保留高度 >= 1 的落点。"""
    tgt = slice(1, m - dy + 1)          # 落点 1..m-dy
    src = slice(dy + 1, m + 1)          # 起点 dy+1..m，落差正好 dy
    nxt_tap[tgt] = [a if a < b else b for a, b in zip(nxt_tap[tgt], tap[src])]
    nxt_cnt[tgt] = [a if a > b else b for a, b in zip(nxt_cnt[tgt], cnt[src])]


def pass_pipe(nxt_tap: list[int], nxt_cnt: list[int], gap: tuple[int, int], m: int) -> None:
    """过管转移：缝隙 (low, high) 外的高度撞管坠毁，缝隙内存活者通过计数 +1。"""
    low, high = gap
    nxt_tap[1:low + 1] = [INF] * low                # 撞下边沿及其下方
    nxt_tap[high:m + 1] = [INF] * (m + 1 - high)    # 撞上边沿及其上方
    nxt_cnt[1:low + 1] = [-1] * low
    nxt_cnt[high:m + 1] = [-1] * (m + 1 - high)
    # 计数只加在存活者身上：-1 表示该高度本就不可达
    nxt_cnt[low + 1:high] = [v + 1 if v >= 0 else -1 for v in nxt_cnt[low + 1:high]]


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n = next(data)                      # 界面长度：横坐标 0..n-1，走完 n 步到最右边
    m = next(data)                      # 界面高度：存活高度 1..m，0 即坠毁
    k = next(data)                      # 管道数

    # 每列一行 (X, Y)：点一次上升 X[x]，一次不点下降 Y[x]
    steps = [(next(data), next(data)) for _ in range(n)]

    # pipe_at[x] = (L, H)：缝隙是开区间 (L, H)，贴边即撞管
    pipe_at: list[tuple[int, int] | None] = [None] * n
    for _ in range(k):
        p, low, high = next(data), next(data), next(data)
        pipe_at[p] = (low, high)

    tap = [0] * (m + 1)                 # 当前列各高度的最少点击数（列 0 任选高度出发）
    cnt = [0] * (m + 1)                 # 当前列各高度的最多通过管道数
    best = 0                            # 全局最多通过数：路径随时可能坠毁，要逐列取最大

    for x in range(n):
        dx, dy = steps[x]                # 本列的上升/下降步长
        nxt_tap = [INF] * (m + 1)
        nxt_cnt = [-1] * (m + 1)
        rise(nxt_tap, nxt_cnt, tap, cnt, dx, m)
        fall(nxt_tap, nxt_cnt, tap, cnt, dy, m)

        # 落在下一列 x+1 的管道上：缝隙外坠毁，缝隙内通过计数 +1
        gap = pipe_at[x + 1] if x + 1 < n else None
        if gap is not None:
            pass_pipe(nxt_tap, nxt_cnt, gap, m)

        best = max(best, max(nxt_cnt))
        tap, cnt = nxt_tap, nxt_cnt

    fewest = min(tap[1:])               # 列 n：任一高度抵达即通关
    won = fewest < INF
    print(1 if won else 0)
    print(fewest if won else best)


if __name__ == "__main__":
    solve()

复杂度

  • 时间复杂度：O(n⋅m)O(n \cdot m)——每列三次线性扫描（升序点击链、下降切片、有管道时的过滤切片），n⋅m⩽107n \cdot m \leqslant 10^7；相对朴素的 O ⁣(n⋅m⋅m/X[x])O\!\left(n \cdot m \cdot m / X[x]\right)，省掉的正是逐个枚举点击次数的那一维。
  • 空间复杂度：O(m)O(m)——tap/cnt 与 nxt_tap/nxt_cnt 四个滚动数组，外加两份 O(n)O(n) 输入缓存。
  • 本地用题目仓的 20 组真实数据实测全部 PASS，最大规模（n=10000, m=1000n = 10000,\ m = 1000）约 0.9 s0.9\,\mathrm{s}、峰值内存约 17 MB17\,\mathrm{MB}；相对 OJ 的 1000 ms1000\,\mathrm{ms} 限时，Python 侧存在 TLE 风险，但算法与 C++ 正解同阶，不属于以暴力换时间。

总结

  • 小鸟在每个横坐标只有"高度"一个自由度，历史不影响未来 → 按列滚动的一维 DP，状态就是存活高度。
  • 任意次点击不是分支爆炸的来源：点 tt 次 = 沿步长 X[x]X[x] 的链走 tt 步，一次升序扫描（完全背包式正序更新）就把所有 tt 收齐，上升、下降、管道过滤全部压成每列三次 O(m)O(m) 的线性操作。
  • 管道是"节点过滤 + 计数"：缝隙 (L,H)(L, H) 外整段切片置死即"贴边撞管"，缝隙内 +1+1 即"通过"；失败路径由不可达自然表达。
  • 最少点击（min⁡\min）与最多过管（max⁡\max）共享同一张转移图，一趟 DP 同时维护；失败答案要逐列取最大，因为路径可能早已坠毁。

图示解析

这张图串起本题从建模到得到两行答案的主线：

text
题面建模：每格只有"点 t 次上升（到顶封顶）"与"不点下降"，贴地、贴管即死
|- 朴素做法：枚举每格点击数 t → O(n·m²/X)，重复计算同一条链
`- 关键观察：点 t 次 = 沿 h→h+dx 的链走 t 步，每步代价 +1
   `- 一维滚动 DP，每列 O(m)：升序链式递推 → 下降切片 → 缝隙过滤
      `- 同一趟 min/max 双聚合：可通关输出最少点击，否则输出最多过管

先看中间那条关键观察：它把"枚举点击次数"改写成"沿高度链走步"，是整个优化的支点。再看它如何决定实现顺序——先上升链后下降，链里才不会混入下降值。最后注意两个答案共享同一次扫描，只在聚合算子上分道扬镳。