NOIP2005提高组复赛第二题_过河分析

余年寄山水
508次浏览
2021年02月23日 09:28
最佳经验
本文由作者推荐

-

2021年2月23日发(作者:兴趣爱好特长)


过河




【问题描述】


在河上有一座独木桥,


一只青蛙想沿着独木桥从河的一侧跳到另 一侧。


在桥上


有一些石子,


青蛙很讨厌 踩在这些石子上。


由于桥的长度和青蛙一次跳过的距离都是正整数,

我们可以把独木桥上青蛙可能到达的点看成数轴上的一串整点:


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

< p>
个不同的正整数分别表示这


M


个石子在数轴上的位 置(数据保证桥的起点和终点处没有石子)


。所有相邻的整数之间用

一个空格隔开。



【输出文件】输出文件

< br>


只包括一个整数,表示青蛙过河最少需要踩到的石子数。



方法


1


:搜索



•直叙式搜索不行:搜索桥有困难


(桥的长度

< br>1..109


)


;搜索石子更困难


,


(石头的分布是没有


任何规律)



•优化:以桥的长度为对象搜索


+


巧妙 的剪枝



•分析:从桥的一侧到另一侧,中间最多只有


100


个石子。假设桥长为最大值


(109)< /p>


,石头数


也为最大值


(100)


,


则中间一定会有很多


“


空长条


” (


两个石子中的空地


)< /p>


,


关键是如何在处理时


把这些“空长条” 跳过,使得运算次数降到


M


次。



先求出青蛙可能跳到的所有位置,


然后就可以在忽略


“


空长条


”


的前提下,


计算青蛙过河最少


需要踩到的石子数了。算法的时间复杂度为


O(m2)


方法


2


、 动态规划



设


opt[n]

< p>
为青蛙到达


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


也是非负整数。证毕


.


由于题目给出的一个区间是

< p>
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

< p>
的一次跳跃距离跳至


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


< p>
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


位置位于

< p>
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]

< p>
或者为


a[i-1,v]+1


(

< br>j=0


时,即踩到了桥上的第


i


个石子)


。但


究竟


v

< br>多大时,才能使得最少石子数最少呢,我们无法预知,只能在


0

< br>‥


t-1


的范围内一一


枚举


v


,从中找出经过的最少石子数。




a[i,j]=

-


-


-


-


-


-


-


-