形式化题目

数轴上的整点 $0,1,\dots,L$ 表示一座独木桥，青蛙从 $0$ 出发，每次跳跃距离可任选 $[S,T]$ 内的整数，方向固定朝 $L$；当某次跳跃落到或越过 $L$ 时视为过河。桥上给定 $M$ 个互不相同的石子位置（$0$ 和 $L$ 处没有石子），求一条过河路径最少踩到的石子数。其中 $1 \leqslant L \leqslant 10^9$，$1 \leqslant S \leqslant T \leqslant 10$，$1 \leqslant M \leqslant 100$。

样例 $L=10$，$S=2$，$T=3$，石子 $\{2,3,5,6,7\}$，答案为 $2$：首跳只能落在 $2$ 或 $3$，两者都是石子，所以至少踩 $1$ 块；站在 $4$ 时下一跳只能落在 $6$ 或 $7$，也都是石子，于是至少 $2$ 块。走 $0\to2\to4\to6\to8\to10$ 恰好踩 $\{2,6\}$ 两块，故答案恰为 $2$。

正解

思路

朴素做法：设 $dp[i]$ 为落到点 $i$ 时已踩的最少石子数，则

最终答案是 $\min_{i \in [L-T,\,L-1]} dp[i]$（落在该区间内任一点都能一步跳过终点）。直接对 $0..L$ 逐点算需要 $O(LT)$，而 $L \leqslant 10^9$，直接不可行——瓶颈只在于桥太长。

瓶颈分析：石子只有 $M \leqslant 100$ 块，桥上绝大多数位置没有石子；超长的差距全部集中在少数几个"无石子长段"里。因此问题转化为：一个无石子段能被截短到什么程度而不改变答案？

关键观察——窗口最小值的稳定性。设无石子段从点 $x$ 之后开始（$x$ 是段前最后一个特殊点），记

• 段内所有转移窗口都落在 $x$ 右侧时，窗口里的值 $\geqslant c$；而 $dp[x+1],\dots,dp[x+T]$ 各自的窗口并起来恰好覆盖 $[x+1-T,\ x+T-S]$，故 $c$ 也等于这段区间上的最小值，且该最小值一定会在点 $x+2T-S$ 之前被某个段内点取到。
• 把转移窗口逐层展开：对段内点 $i$，有 $dp[i] = \min dp[\text{low}..u]$，其中 $\text{low}$ 在 $[x+1-T,\ x+1]$ 内随 $i$ 循环，$u = i - S\left\lfloor \frac{i-x-1}{T} \right\rfloor - S$ 随 $i$ 严格变大。当 $u \geqslant x+2T-S$ 时，$[x+1, u]$ 内已出现取到 $c$ 的点，而 $\text{low}$ 左侧那截的最小值 $\geqslant c$，于是 $dp[i] = c$。

由此得到：只要段长不小于

段内从点 $x+H$ 起 $dp$ 恒等于 $c$，与段长无关；进出该段的行为只依赖 $c$。因此把每个无石子段截到 $B = H + T$（多留 $T$ 保证段尾整段落在恒定区）不会改变最终答案。注意截断的正确形式是把该特殊点及其之后的所有点整体左移（等价于对原始间距取 $\min(\text{gap}, B)$），因为只挪动一块石子会改变它与后继的间距，破坏相对结构。

压缩后桥长不超过 $(M+1) \cdot B$；$T \leqslant 10$ 时 $B \leqslant 201$，即 $L' \leqslant 101 \times 201 \approx 2 \times 10^4$，逐点 DP 完全可行。以 $S=1,T=2$（$B=9$）为例：

$S = T$ 特判：跳跃距离固定，路径被唯一确定为 $0, S, 2S, \dots$，青蛙必然踩到每一个 $S$ 的倍数点，所以答案就是"位置是 $S$ 的倍数"的石子个数，$O(M)$ 直接数完。

压缩实例上的逐点 DP 以样例演示（$\infty$ 表示尚不可达）：

观察重点：$dp[1]=\infty$ 是因为 $i < S$ 还没有合法起跳点；从 $i=4$ 起窗口开始滑动取前缀最小值，$dp$ 单调不增地传播。答案取 $\min(dp[7..9]) = 2$，与样例一致。

代码

main.py 按上述推导实现：先特判 $S = T$；否则算出 $B$，对每个原始间距累加 $\min(\text{gap}, B)$ 得到压缩桥 $L'$，再逐点滚动窗口 DP，最后取尾窗最小值。

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/**
 * 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;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    ll length;
    int min_jump, max_jump, stone_count;
    cin >> length >> min_jump >> max_jump >> stone_count;
    vector<ll> stones(stone_count);
    for (int i = 0; i < stone_count; i++) cin >> stones[i];
    sort(stones.begin(), stones.end());

    // S == T：每次跳固定距离，必踩所有 S 的倍数点
    if (min_jump == max_jump) {
        int ans = 0;
        for (int i = 0; i < stone_count; i++)
            if (stones[i] % min_jump == 0) ans++;
        cout << ans << "\n";
        return 0;
    }

    // 截断：每段间距取 min(gap, cap)
    int period = max_jump - min_jump;
    int lead = (2 * max_jump - 1 + period - 1) / period;
    int cap = 1 + max_jump + max_jump * lead;

    vector<ll> crossed;
    ll prev_orig = 0, new_pos = 0;
    for (int i = 0; i <= stone_count; i++) {
        ll pos = (i < stone_count) ? stones[i] : length;
        new_pos += min(pos - prev_orig, (ll)cap);
        crossed.push_back(new_pos);
        prev_orig = pos;
    }
    ll bridge = crossed.back();
    set<ll> has_stone(crossed.begin(), crossed.end() - 1);

    vector<int> dp(bridge + 1, INF);
    dp[0] = 0;
    for (ll i = 1; i <= bridge; i++) {
        if (i < min_jump) continue;
        int best = INF;
        ll lo = max(0LL, i - max_jump);
        ll hi = i - min_jump;
        for (ll j = lo; j <= hi; j++)
            if (dp[j] < best) best = dp[j];
        if (best < INF)
            dp[i] = best + (has_stone.count(i) ? 1 : 0);
    }
    int ans = INF;
    ll lo = max(0LL, bridge - max_jump);
    for (ll i = lo; i <= bridge; i++)
        if (dp[i] < ans) ans = dp[i];
    cout << ans << "\n";
    return 0;
}

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#!/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
# update_at: 2026-10-02

import sys

INF = 10**9  # 不可达代价：石子至多 100 块，INF 远大于任何合法答案


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    length = next(data)                                   # 桥长 L
    min_jump, max_jump, stone_count = next(data), next(data), next(data)
    stones = sorted(next(data) for _ in range(stone_count))

    # S == T：每次跳固定距离，路径被唯一确定，青蛙必踩所有 S 的倍数点
    if min_jump == max_jump:
        print(sum(1 for pos in stones if pos % min_jump == 0))
        return

    # 无石子长段的 DP 值超过 cap 后恒定（推导见题解），每段截到 cap 即可
    period = max_jump - min_jump                          # T - S，窗口增长量
    lead = (2 * max_jump - 1 + period - 1) // period      # ceil((2T-1)/(T-S))
    cap = 1 + max_jump + max_jump * lead                  # B = H + T

    # 截断 = 把该点及之后的整体左移，等价于对「原始间距」逐段取 min(gap, cap)
    crossed: list[int] = []
    prev_orig = new_pos = 0
    for pos in stones + [length]:
        new_pos += min(pos - prev_orig, cap)
        crossed.append(new_pos)
        prev_orig = pos

    bridge = crossed[-1]                                  # 压缩后的桥长 L'
    has_stone = set(crossed[:-1])

    # 逐点 DP：dp[i] = 窗口 [i-T, i-S] 的最小代价 + 本点石子
    dp = [INF] * bridge
    dp[0] = 0
    for i in range(1, bridge):
        if i < min_jump:                                  # 还没有合法起跳点
            continue
        dp[i] = min(dp[max(0, i - max_jump):i - min_jump + 1]) + (i in has_stone)

    # 落在 [L-T, L-1] 内任意一点都能一步跳过终点，取其中最小代价
    print(min(dp[max(0, bridge - max_jump):bridge]))


if __name__ == "__main__":
    solve()

复杂度

• 时间复杂度：$O\big((M+1) \cdot B \cdot (T-S+1)\big)$，$B = 1 + T + T\left\lceil \frac{2T-1}{T-S} \right\rceil \leqslant 201$，最坏约 $2\times10^5$ 次基本操作；$S = T$ 时为 $O(M)$。
• 空间复杂度：$O\big((M+1) \cdot B\big)$，DP 数组长度不超过 $2.1\times10^4$，远小于 32 MB 限制。

总结

本题的核心是把 $10^9$ 的桥压到可算规模：朴素 DP 的瓶颈不在石子（只有 100 块）而在桥长，无石子长段的 DP 值经过 $H = 1 + T\lceil (2T-1)/(T-S)\rceil$ 个位置后恒等于进入段前的窗口最小值 $c$，与段长无关，所以逐段截到 $B = H + T$ 不改变答案——截断必须以"后缀整体左移"的形式进行，保证点间相对结构不变。$S = T$ 则退化为数 $S$ 的倍数石子。实测 10 组真实数据全部一致，最难点约 0.1 s，相对 1000 ms / 32 MB 的限制十分宽裕。