【每日一题】5月9日题目精讲

题号 NC16655
名称 过河
来源 NOIP2005提高组复赛
戳我进入往期每日一题汇总贴~
往期每日一题题单



如果你在题库做题时遇到了喜欢的题目，欢迎推荐给邓老师~ 点击查看详情

题解

先不考虑开不下数组的问题
如果我们用f[i]表示走到i这个位置的最小的踩石子的次数话
i这个位置没有石头：f[i]=min(f[i],f[k])
i这个位置是石头：f[i]=min(f[i],f[k]+1)
(k是上一步的位置，)
现在我们来解决桥太长了数组开不了的问题，我首先仔细看数据范围，相对于桥长度L，石头个数和青蛙跳跃范围S，T都是很小的，也就是说总是存在一些石头离得非常远，从前一个石头到这个石头需要跳很多步才能到达，而只要S和T不等，那么在这漫长的跳跃中我们总可以调整步幅使得踩不到这颗石子。换句话说，只要S和T不等当两个石子之间的距离超过了一定范围之后，任意距离都是可以到达的，这个时候两个离得很远的石头之间的距离就不重要了，那么现在我们就来考虑这个距离是多少：
（其实如果是比赛的时候，你其实可以根据时空限制直接估算这个值，能卡着时空过就行了）
我们先看例子，当S=3，T=4的时候那些长度是可以到达的：
3 、4、 6=3+3、 7=3+4、 8=4+4、 9=3+3+3、 10=3+3+4、 11=3+4+4、 12=4+4+4/3+3+3+3、13、14、15……
S=5，T=6时:
5、6、10=5+5、11=5+6、12=6+6、15=5+5+5、16=5+5+6、17=5+6+6、18=6+6+6、20=5+5+5+5、21=5+5+5+6、22=5+5+6+6、23=5+6+6+6、24=6+6+6+6、25=5+5+5+5+5、26=5+5+5+5+6、27=5+5+5+6+6、28=5+5+6+6+6、29=5+6+6+6+6、30=6+6+6+6+6/5+5+5+5+5+5……
我们发现，当长度超过之后，这个长度会有至少两种跳的方式（T个S相加和S个T相加），之后我们可以在每一步比都在较小的那种方法（T个S相加）的基础上将某些步的长度变大，然后就可以跳出更长的长度，也就是说及其之前的所有长度都可以跳出来，然后自然也有它自己的表达方式，之后的长度也都可以在S的整数倍的基础上调整得来。
对于本题来说，最大的的取值是，也就是说我们让任意两个距离大于90的石头距离为90就可以了，这样时间空间都满足了!
（S==T的情况直接特判）

看完邓老师的题解，记得去做题提高呀~
欢迎各位大佬来做题写题解，也欢迎大家踊跃在当日讨论贴中提问！

活动奖励：

在牛客博客中写出题解，并回复地址
审核通过可获得（依据题目难度和题解的内容而定）

本道题目5月16日中午12：00之前写的题解有获得牛币资格~

.牛币兑换中心

牛客博客开通方式

1. 如何开通牛客博客：https://www.nowcoder.com/discuss/202952
2. 如何使用博客搬家功能：进入博客--->设置--->底部博客搬家
3. 如果你对牛客博客有任何意见或建议：牛客博客意见反馈专贴