本文共 1312 字，大约阅读时间需要 4 分钟。

为了解决这个问题，我们需要找到青蛙过河最少需要踩到的石子数。青蛙每次跳跃的距离在给定的范围内，桥上有一些石头，我们需要计算青蛙过河时必须踩到的石头的最小数量。

方法思路

解决代码

import bisect
L = int(input())
S, T, M = map(int, input().split())
stones = list(map(int, input().split()))
stones.sort()
n = len(stones)
INF = float('inf')
dp = [INF] * (L + 1)
dp[0] = 0
for i in range(L + 1):
    if dp[i] == INF:
        continue
    for d in range(S, T + 1):
        j = i - d
        if j < 0:
            continue
        if j > L:
            continue
        if j >= L:
            if dp[j] < dp[i]:
                dp[i] = dp[j]
        else:
            if i >= L:
                count = 0
            else:
                left = bisect.bisect_left(stones, j + 1)
                right = bisect.bisect_right(stones, i - 1)
                count = right - left
            if dp[j] + count < dp[i]:
                dp[i] = dp[j] + count
print(dp[L])

代码解释

通过这种方法，我们可以高效地找到青蛙过河最少需要踩到的石头数目。

转载地址：http://iojfk.baihongyu.com/