过河的最短时间

Question

一只青蛙正试图到达河的另一边.最初位于银行的一侧(位置-1)并且想要到达银行的另一侧(位置N).

青蛙可以跳到1到D之间的任何距离.如果D小于N,青蛙不能直接跳跃.有一些石头可以帮助青蛙跳跃,但是只有在一定时间后水会不断减少,它们才会离开水面.只有当石头没有水时,青蛙才能跳进石头.河流中的石头在阵列A中描述,由N个整数组成.A [K]表示位置K处的石头将离开水的时间.A [K] = - 1表示该位置没有石头.目标是找到青蛙可以到达另一家银行的最早时间.

实施例D = 3,N = 6.
A [0] = 1

A [1] = - 1

A [2] = 0

A [3] = 2

A [4] = 3

A [5] = 5

在时间2,3个石头将缺水,青蛙可以跳3次跳到另一个岸.

有人可以帮我解决这个问题吗？我想不出一个有效的方法来解决这个问题.

Answer 1

这是一个可能的解决方案:

通过将index(i)推进到stone(A[i])并使用该范围中的最低时间来迭代数组A[i+1..i+D].在每个步骤中,保持到目前为止找到的最大时间(maxTime = max(maxTime, A[i]).只要重复此过程即可i < N-D.完成此过程后,将找到最长时间maxTime.

复杂度为O((ND)D).