题解 | #过河#

对python来说，本题真正的难点在于l很大时如何不超时。 为此需要运用数论做一些粗浅的算法优化。

实际上还有很多能抠的细节没有抠，因为在python上的运行速度已经比较令人满意了，再去深究一些不能改变运算量数量级的地方意义不大。

注：由irises1412提供的答案应该是错误的，它通不过示例自测。

# 对python来说，本题真正的难点在于l很大时如何不超时。
l = int(input())
s, t, m = list(map(int, input().split()))
sts = list(map(int, input().split()))
sts = sorted(sts)

# 化简原问题来减少计算量：假设位置为i,j的两个石头之间的距离 j-i > 2*s*t，
# 那么实际上跳到第j个位置最少踩的石头数量就等于跳到第j-s*t个位置最少踩的石头数量。
# 于是在l很大时，计算量从O(l)减少到O(s*t*m)
sts = [0] + sts + [l]
for i in range(1, m + 2):
    d = sts[i] - sts[i - 1]
    if d > 2 * s * t:
        r = d % (s * t)
        if r == 0:
            minus = d - 2 * s * t
        else:
            minus = d - r - s * t
        sts[i : m + 2] = [sts[j] - minus for j in range(i, m + 2)]
sts, l = sts[1:-1], sts[-1]

# 动态规划：这里建立了长度为t的动态规划列表，但可读性和速度可能不如用长度为新l的列表。
# 初始化动态规划
dp = [float("inf") for _ in range(t)]
dp[0] = 0
for i in range(1, t):
    choice = dp[max(0, i - t) : max(0, i - s + 1)]
    if choice:
        dp[i] = min(choice) + (i in sts)

# 进行动态规划
for i in range(t, t + l):
    choice = dp[: t - s + 1]
    if choice:
        dp = dp[1:] + [min(choice) + (i in sts)]
    else:
        dp = dp[1:] + [float("inf")]

print(min(dp))