讨论 / Possible Solution
Magna_Medivh 2017-07-31 07:05:31
点我顶贴 收藏 删除
总长度L很长,但是石头数(关心点)很少,考虑离散化。但是离散化标准若是石头所在点是不行的,因为跳跃是连贯过程。但是L显然是冗余的,所以考虑“缩路”:我不关心相邻两石头间是怎么跳的,只关心要到下一块石头时青蛙与下一块石头间的可能距离。然而,若两石头间距离很长,则要到下一块石头时青蛙与下一块石头间的可能距离可以是s到t的任意值(显然),故距离再长就没意义了,而这个上界(粗略)便是9*10,于是L可以缩到90 * 100 << 9 * 10^9
查看更多回复
提交回复