NOIP2005提高组复赛第二题_过河分析
-
过河
【问题描述】
在河上有一座独木桥，
一只青蛙想沿着独木桥从河的一侧跳到另
一侧。
在桥上
有一些石子，
青蛙很讨厌
踩在这些石子上。
由于桥的长度和青蛙一次跳过的距离都是正整数，
我们可以把独木桥上青蛙可能到达的点看成数轴上的一串整点：
0
< br>，
1
，
……
，
L
（其中
L
是
桥的长度）
。坐标为
0
的点表示桥的起点，坐标为
L
的点表示桥的终点
。青蛙从桥的起点开
始，不停的向终点方向跳跃。一次跳跃的距离是
S
到
T
之间的任意正整数（包括<
/p>
S,T
）
。当
青
蛙跳到或跳过坐标为
L
的点时，就算青蛙已经跳出了独木桥。<
/p>
题目给出独木桥的长度
L
，青蛙跳跃的距离范围
S,T
，桥上石子的位置。你
的任务是确定青
蛙要想过河，最少需要踩到的石子数。
【输入文件】输入文件
的第一行有一个正整数
L
（
1
≤
L
≤
109
）
，表示独木桥
的长度。第二行有三个正整数
S
，
T
，
M
，分别表示青蛙一次跳跃的最小距离，最大距离，
及桥上石子
的个数，其中
1≤S≤T≤10
，
1≤
M≤
100
。第三行有
M
个不同的正整数分别表示这
M
个石子在数轴上的位
置（数据保证桥的起点和终点处没有石子）
。所有相邻的整数之间用
一个空格隔开。
【输出文件】输出文件
< br>
只包括一个整数，表示青蛙过河最少需要踩到的石子数。
方法
1
：搜索
•直叙式搜索不行：搜索桥有困难
（桥的长度
< br>1..109
）
；搜索石子更困难
,
（石头的分布是没有
任何规律）
•优化：以桥的长度为对象搜索
+
巧妙
的剪枝
•分析：从桥的一侧到另一侧，中间最多只有
100
个石子。假设桥长为最大值
(109)<
/p>
，石头数
也为最大值
(100)
，
则中间一定会有很多
“
空长条
” (
两个石子中的空地
)<
/p>
，
关键是如何在处理时
把这些“空长条”
跳过，使得运算次数降到
M
次。
先求出青蛙可能跳到的所有位置，
然后就可以在忽略
“
空长条
”
的前提下，
计算青蛙过河最少
需要踩到的石子数了。算法的时间复杂度为
O(m2)
方法
2
、
动态规划
设
opt[n]
为青蛙到达
n
位置最少需要踩到的石子数。
rock[n]=
这个方程的时间复杂度是
O
（
n<
/p>
）级的
，显然在竞赛时限内，
n≤109<
/p>
的极限数据是无法出
1
0
n
位置有石子
n
位置无石子
opt
[
n
]
m
in
{
opt
[
n
i
]
rock
[
n
]}
S
i
T
解的
优化方法：压缩法
•结论：
•若（采用跳跃距离
p
和
p+1
时可以跳
至任何位置
Q
）
，则在
Q
≥
P*
（
< br>P-1
）时是一定有解的。
p
x
(
p
<
/p>
1
)
y
Q
为什么呢？
Because
证明
•
由于
p<
/p>
与
p+1
间隔
1
,
故方程
px+(p+1)y=Q
有整
数解，设其解为
• x=x0+(p+1)t,y=y0
-pt(t
是整数
)
•
取适当的
t
，使得
0
≤
x
≤
< br>p(
只需在
x0
上加上或减去若
干个
p+1),
则当
Q>p(p-1)
-1
时，有
•
（
p+1
）
y=Q-px>p(p-
1)-1-px
≥
p(p-1)-1-p*p=-(p+1)
•
于是
y>-1
，故
y
≥
0
也是非负整数。证毕
.
由于题目给出的一个区间是
1≤S≤T≤10
，于是当相邻的两个石子之间的距离不小于
8*9=72
时，则后面的距离都可以到达，我们就可以认为它们之间的距离
就是
72
。如此一来，我们
就将原题<
/p>
L
的范围缩小为了
100*72=720
0
，动态规划算法完全可以承受了。但是当
S=T
时，
上述等式是无法使用的，在这种情况下，只需要在所有石子中，统计出坐
标是
S
倍数的石
子个数就可以了。
设
n
为桥上的石子数（
1≤n≤m
）
；
b[i]
为能否用
s
到
t
的一次跳跃距离跳至
i
远的标志
< br>
b[i]=true
i=0
b[i]=
1≤i≤90
c[v]
为青蛙能否跳到相对距离为
v
远的标志（
v≤90
）
•
•
c[v]=
a[i,j]
为青蛙跳至
x[i]
左方相对距离为
j
的位置时所经过的最少石子总数。
若
j=0
，
说明青蛙踩
false
true<
/p>
b
[
v
]
v
0
v
s
(
s
1
)
0
v
s
(
s
<
/p>
1
)
到了桥上的第
i
个石子。初始时，
a[i,j]=n+1
< br>（
0
≤
i
≤
n
，
0
≤
j
≤
t-1
）
。
第
1
种情况：
x[i]-j
< br>位置位于
x[i-1]
的左方，即
x[i]-j
≤
x[i-1]
显然，
跳至
x[i]-j
位置经过的最少石子总数为
< br>a[i-1,j-x[i]+x[i-1]]
第
2
种情况：
x[i]-j
位置位于
x[i-1]
的右方，即
x[i]-j>x[i-
1]
显然，如果青蛙能够由
x[i-1]-v
位置跳至
x[i]-j
位置（
can(x[i]-j-x[i
-1]+v)=true
）
，则跳至
x
[i]-j
位置经过的石子总数为
a[i-1,v]
或者为
a[i-1,v]+1
（
< br>j=0
时，即踩到了桥上的第
i
个石子）
。但
究竟
v
< br>多大时，才能使得最少石子数最少呢，我们无法预知，只能在
0
< br>‥
t-1
的范围内一一
枚举
v
，从中找出经过的最少石子数。
a[i,j]=