题目名称	111. [NOIP 2005]过河
输入输出	`river.in/out`
难度等级	★★★
时间限制	1000 ms (1 s)
内存限制	128 MiB
测试数据	10
题目来源	BYVoid 于2008-09-17加入
开放分组	全部用户
提交状态
分类标签	动态规划 NOIP/CSP 离散化状态压缩
查看题解	分享题解

通过：332，提交：1368，通过率：24.27%
Sky_miner	100	0.000 s	0.00 MiB	C++
LOSER	100	0.000 s	0.00 MiB	C++
YGOI_真神名曰驴蛋蛋	100	0.000 s	0.00 MiB	C++
YGOI_真神名曰驴蛋蛋	100	0.000 s	0.00 MiB	C++
rvalue	100	0.000 s	0.00 MiB	C++
Hzoi_Queuer	100	0.000 s	0.00 MiB	C++
浮生随想	100	0.000 s	0.00 MiB	C++
牧殇	100	0.000 s	0.00 MiB	C++
哒哒哒哒哒！	100	0.000 s	0.00 MiB	C++
哒哒哒哒哒！	100	0.000 s	0.00 MiB	C++

本题关联比赛
防止颓废的小练习v0.4
假期找点事儿做题吧
ctime蒟蒻生日赛
状态压缩DP
状态压缩DP练习

关于过河的近10条评论(全部评论)
既然超过 $S \cdot T$ 的空地不会改变青蛙的“记忆模式”，我们就可以把任意长的空地缩短成 $S \cdot T$，而不影响最终答案。例如，若石子在 100 和 10000 处，中间 9900 格全是空的，我们只需保留 90 格（因 $S,T \leq 10$，取 $10 \times 9 = 90$）。压缩后，DP 状态空间大小从 $L$（可能 10⁹）降到约 $100 \times 90 = 9000$，计算可行。这个 $S \cdot T$ 就是保证状态“线性无关组已完备”的临界长度。金牌教师王艳芳 2025-10-23 22:55 31楼
假设两块石子之间全是空地，距离为 $d$。青蛙能跳 $S, S+1, \dots, T$ 格。数学上可以证明：只要 $d > S \cdot T$，青蛙就能通过不同跳法，落到这段空地之后的任意“相对位置”（比如刚好对齐某个余数）。这是因为步长集合能“生成”所有足够大的数（因 $\gcd=1$），而 $S \cdot T$ 是最坏情况下需要的最小长度（来自 Frobenius 问题）。此时，状态向量 $\mathbf{v}_x$ 已经遍历了所有可能的组合，新增的空地不会带来新信息——就像背完乘法表后，再背也是重复。金牌教师王艳芳 2025-10-23 22:54 30楼
青蛙跳到位置 $x$ 时，最少踩多少石子，只和它前 $T$ 步的情况有关（因为最多跳 $T$ 格）。我们可以把这 $T$ 个值写成一个“状态向量”： \[ \mathbf{v}_x = \begin{bmatrix} f(x-T+1) \\ f(x-T+2) \\ \vdots \\ f(x) \end{bmatrix} \] 这个向量就像青蛙的“记忆”，长度固定为 $T$。所以，不管桥多长，所有可能的“记忆”最多只有 $T$ 个独立方向——这叫状态空间维度不超过 $T$。一旦走过一段很长的空地，这些“记忆”就会开始重复。金牌教师王艳芳 2025-10-23 22:54 29楼
以下内容是根据陈老师讲的后增加的自我总结的内容金牌教师王艳芳 2025-10-23 22:54 28楼
500分留念感谢小青蛙给一个机会题解已发布冷月星云 2021-11-25 18:31 27楼
小凯的疑惑当s=9，t=10；互质；最小不可拼出的为s*t-s-t；即71；雾茗 2019-03-23 15:40 26楼
2520压缩法。。 Moon_ 2018-10-28 20:10 25楼
我傻。 Fisher. 2017-10-31 15:31 24楼
第一发状态压缩动态规划 JustWB 2017-10-30 21:13 23楼
我只说，小心压缩两个石头到同一位置。。。皓芷 2017-07-03 16:19 22楼

111. [NOIP 2005]过河

★★★ 输入文件：river.in 输出文件：river.out 简单对比
时间限制：1 s 内存限制：128 MiB

【问题描述】

在河上有一座独木桥，一只青蛙想沿着独木桥从河的一侧跳到另一侧。在桥上有一些石子，青蛙很讨厌踩在这些石子上。由于桥的长度和青蛙一次跳过的距离都是正整数，我们可以把独木桥上青蛙可能到达的点看成数轴上的一串整点： $0,1,\cdots,L$(其中 $L$ 是桥的长度)。坐标为 $0$ 的点表示桥的起点，坐标为 $L$ 的点表示桥的终点。青蛙从桥的起点开始，不停的向终点方向跳跃。一次跳跃的距离是 $S$ 到 $T$ 之间的任意正整数（包括 $S,T$ ）。当青蛙跳到或跳过坐标为 $L$ 的点时，就算青蛙已经跳出了独木桥。

题目给出独木桥的长度 $L$ ，青蛙跳跃的距离范围 $S,T$ ，桥上石子的位置。你的任务是确定青蛙要想过河，最少需要踩到的石子数。

【输入文件】

输入文件的第一行有一个正整数 $L(1\leq L\leq 10^9)$，表示独木桥的长度。第二行有三个正整数 $S,T,M$ ，分别表示青蛙一次跳跃的最小距离，最大距离，及桥上石子的个数，其中 $1\leq S\leq T\leq 10,1\leq M\leq 100$ 。第三行有 $M$ 个不同的正整数分别表示这 $M$ 个石子在数轴上的位置（数据保证桥的起点和终点处没有石子）。所有相邻的整数之间用一个空格隔开。

【输出文件】

输出文件只包括一个整数，表示青蛙过河最少需要踩到的石子数。

【输入样例】

10
2 3 5
2 3 5 6 7

【输出样例】

【数据规模】

对于30%的数据，$L\leq 10000$；
对于全部的数据，$L\leq 10^9$。

关于过河的近10条评论(全部评论)
既然超过 \(S \cdot T\) 的空地不会改变青蛙的“记忆模式”，我们就可以把任意长的空地缩短成 \(S \cdot T\)，而不影响最终答案。例如，若石子在 100 和 10000 处，中间 9900 格全是空的，我们只需保留 90 格（因 \(S,T \leq 10\)，取 \(10 \times 9 = 90\)）。压缩后，DP 状态空间大小从 \(L\)（可能 10⁹）降到约 \(100 \times 90 = 9000\)，计算可行。这个 \(S \cdot T\) 就是保证状态“线性无关组已完备”的临界长度。金牌教师王艳芳 2025-10-23 22:55 31楼
假设两块石子之间全是空地，距离为 \(d\)。青蛙能跳 \(S, S+1, \dots, T\) 格。数学上可以证明：只要 \(d > S \cdot T\)，青蛙就能通过不同跳法，落到这段空地之后的任意“相对位置”（比如刚好对齐某个余数）。这是因为步长集合能“生成”所有足够大的数（因 \(\gcd=1\)），而 \(S \cdot T\) 是最坏情况下需要的最小长度（来自 Frobenius 问题）。此时，状态向量 \(\mathbf{v}_x\) 已经遍历了所有可能的组合，新增的空地不会带来新信息——就像背完乘法表后，再背也是重复。金牌教师王艳芳 2025-10-23 22:54 30楼
青蛙跳到位置 \(x\) 时，最少踩多少石子，只和它前 \(T\) 步的情况有关（因为最多跳 \(T\) 格）。我们可以把这 \(T\) 个值写成一个“状态向量”： \[ \mathbf{v}_x = \begin{bmatrix} f(x-T+1) \\ f(x-T+2) \\ \vdots \\ f(x) \end{bmatrix} \] 这个向量就像青蛙的“记忆”，长度固定为 \(T\)。所以，不管桥多长，所有可能的“记忆”最多只有 \(T\) 个独立方向——这叫状态空间维度不超过 \(T\)。一旦走过一段很长的空地，这些“记忆”就会开始重复。金牌教师王艳芳 2025-10-23 22:54 29楼
以下内容是根据陈老师讲的后增加的自我总结的内容金牌教师王艳芳 2025-10-23 22:54 28楼
500分留念感谢小青蛙给一个机会题解已发布冷月星云 2021-11-25 18:31 27楼
小凯的疑惑当s=9，t=10；互质；最小不可拼出的为s*t-s-t；即71；雾茗 2019-03-23 15:40 26楼
2520压缩法。。 Moon_ 2018-10-28 20:10 25楼
我傻。 Fisher. 2017-10-31 15:31 24楼
第一发状态压缩动态规划 JustWB 2017-10-30 21:13 23楼
我只说，小心压缩两个石头到同一位置。。。皓芷 2017-07-03 16:19 22楼