青蛙过桥
-
描述
Description
在
河上有一座独木桥，
一只青蛙想沿着独木桥从河的一侧跳到另一侧。
在桥上有一些石子，
青蛙很讨
厌踩在这些石子上。由于桥的
长度和青蛙一次跳过的距离都是正整数，我们可以把独木桥上青蛙可能到达
的点看成数轴
上的一串整点：
0
，
1
，……，
L
（其中
L
是桥的长度）。坐标为
0
的点表示桥的起点，坐
标为
L
的点表示桥的终点。青蛙从桥的起点开始，不停的向终点
方向跳跃。一次跳跃的距离是
S
到
T<
/p>
之间的任
意正整数（包括
S,T
）。当青蛙跳到或跳过坐标为
L
的点时，就算青
蛙已经跳出了独木桥。
题目给出独木桥的长度
L
，青蛙跳跃的距离
范围
S,T
，桥上石子的位置。你的任务是确定青蛙要想过
河，最少需要踩到的石子数。
对于
30%
的数据，
L <=
10000
；
对于全部的数据，
L <=
10^9
。
输入格式
Input
Format
输入的第一行有一个正整数
L
（
1 <= L <= 10^9
）
，
表示独木桥的长度。
第二行有三个正整数
S
< br>，
T
，
M
，分别表示青蛙一次跳跃的最小距离，最大距离，及桥上石子的个数，其中
1 <=
S <= T <= 10
，
1 <=
M <= 100
。第三行有
M
个不同的正整数分别表示这
M
个石子在数轴上
的位置（数据保证桥的起点和终
点处没有石子）。所有相邻的整数之间用一个空格隔开。
输出格式
Output Forma
t
输出只包括一个整数，表示青蛙过河最少需要踩到的石子数。
解析：本题目是自己碰到的第一个动态规划题目，遇到的难度也是前所未有。自己只能窘
迫的说水平太低
了，连续提交了十几遍才通过，这还是在参考别人代码的基础上
AC
的。顺别吐槽一下，
Vijos
的系统也实
在太差了，自动删除回车换行打乱格式导致编译通不过，最后还
逼着我换了
firefox
才可以顺利提交。
< br>
思路一：也是自己最开始的思路，我想到了递归求解此问题。虽然对于样例很容
易的通过，但是提交之后
10
组测试数据，没有一对是正确的，
各种窘迫，考虑到数据规模还以为是自己的数据类型定义的太小，还
专门换成了
long
类型，但是提交之后仍然出错，这是关注错误信息，发现给出的
是堆栈溢出，这时候就
是傻子也会想到应该是递归层次太多导致的，看到那个
L
的范围，溢出也是理所应当的。不得不放弃这种
思路，但是自己有不会别的思路，只能参考网友上各种牛们提供的代码。下面是自己的递归代码，还是后
者脸皮贴出来吧。
1.
#include
#include
#include
2.
int
NumStone = 101;
3.
int
IsStone(
int
destinaton,unsigned
int
Stone[],
int
M)
4.
{
5.
int
high = M -1;
6.
int
low = 0;
7.
while
(low <= high)
8.
{
9.
int
mid =
(low + high) / 2;
10.
if
(destinaton == Stone[mid])
11.
return
mid+1;
12.
if
压缩本题是一类很有意思的动态规划题；不同于决策优化，本题要求优化状态，这就使题目增加了很多的
<
br>(10^9)
(destinaton
13.
high = mid - 1;
14.
else
15.
low = mid + 1;
16.
}
17.
return
0;
18.
}
19.
void
select(unsigned
int
a[],
int
count)
/*
将石子出现的位置排序
*/
20.
{
21.
int
i,j,temp;
22.
23.
for
(i=0;i
24.
{
25.
temp=a[i];
26.
j=i-1;
27.
while
(j>=0 && temp
28.
{
29.
a[j+1]=a[j];
30.
j--;
31.
}
32.
a[j+1]=temp;
33.
}
34.
}
35.
void
cal(
int
location,
int
num,
long
int
L,
int
S,
int
T,unsigned
int
Stone[],
i
nt
M)
36.
{
37.
int
swap;
38.
if
(location >= L)
39.
{
40.
if
(num <
NumStone)
41.
{
42.
NumStone = num;
43.
}
44.
}
45.
else
46.
{
47.
for
(swap=S;swap<=T;swap++)
48.
{
49.
if
(IsStone(location,Stone,M))
50.
{
51.
num++;
52.
}
53.
cal(location+swap,num,L,S,T,Stone,M);
54.
}
55.
}
56.
}
57.
int
main()
58.
{
59.
unsigned
int
L;
60.
int
S,T,M,Temp,n;
61.
scanf(
,&L);
62.
scanf(
,&S,&T,&M);
63.
unsigned
int
*Stone =
(unsigned
int
*)malloc(
sizeof
(unsigned
int
)*M);
64.
for
(n=0;n
65.
scanf(
,&Stone[n]);
66.
select(Stone,M);
67.
cal(0,0,L,S,T,Stone,M);
68.
printf(
,NumStone);
69.
system(
);
70.
return
0;
71.
}
思路二：这是人家正统的思想分析，我就直接贴过来吧，代码
也是根据理解写的。方法为动态规划
+
路径
灵活性。
朴素的动态规划注意到当前
状态只与其前面的
T
个状态有关；所以说采用滚筒法可以在
O(LT)
的时间内解决本题。但是，本题中
L
非常大，因此我们希望算法的时间复杂度与
L
无关。
一种想法是：将当前状态
s
与其前面的
T
个状态看作一个长度为
T+1
的状态数组，如果在一次滚筒更新
中新旧
两个数组完全一样，则在遇到下一块石头之前，状态将会完全不变。这个原则是很简单的，因为除
非遇到一块石头，否则每一个决策的前提都是不变的，所以说滚筒更新下去，状态一定不变。
那么，我们就需要问一个问题：究竟会不
会出现这种更新前后状态不变的情况呢？如果不会出现这些情
况，那么算法的优化也就无
从谈起了。事实上，只要
S <
T
，就一定会出现这种情况。
这是很好理解的。假设
S < T
，则
青蛙可以跳
T
步或
T-1
步，这两个步长是互质的。根据扩展的欧几里
德定理，当路程足够长的时候，
一定会出现这样一种情况：前后
T
步全部被同一个数覆盖；这就
可以直接
应用优化了。时间复杂度是
O(NT)
。
从桥的一侧到另一侧，中间最多只有
100
个石子。假设桥长为最大
值
，石头数也为最大值
(100)
，则中间一定会有很多“空长条”
(
两个石子中的空地
)
，关键是如何
在处理时把这些“空长条”跳过，使得运算次数降到
M
次。结论：
若（采用跳跃距离
p
和
p+1
时可以跳
至任何位置
Q
），则在
Q
≥
P*
（
P-1
）时是一定有解的。
Because
证明
由于
p
与
p+1
间隔
1,
故方程