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

通过：327，提交：1276，通过率：25.63%
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条评论(全部评论)
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楼
去年全校大扫除是高一做的，所以今年的全校大扫除应该高二做了，你们也不用觉得不公平，明年就轮到高三做了 Sky_miner 2016-10-14 20:39 21楼
#include<iostream> using namespace std; int main()/阶段是每走一步，状态是起点到该坐标点最小石子数，决策是s-t走几步状态转移方程是f（i）=min{f（i-k）+d【i】）}s《k《t无论怎么说都要跳到i那里直接跳到i那里的石子数是看 i那里有木有而中间不仅要看i还要考虑所以肯定是直接跳到那里为最优决策； / {int d[10000000],stone[101],f[100000000],l,s,t,m; cin>>l>>s>>t>>m; for (int j=1;j<=m;j++) cin>>stone[i]; } 楚修 2016-09-29 21:09 20楼
Hzoi_Yniverse 2016-03-27 13:45 19楼
三点注意： 1、可能输入的石子位置是乱序，应先排序（只是可能，体现程序鲁棒性）。 2、要压缩长度，压缩到t*(t-1）。 3、注意循环越界（&&v>=j）。 _Itachi 2016-03-25 11:12 18楼

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$。