写了知乎文章
https://zhuanlan.zhihu.com/p/361026592

题目描述

https://www.acwing.com/problem/content/description/486/

样例

10
2 3 5
2 3 5 6 7

输出:
2

算法1

(状态压缩dp) $O(M * T^2*(T - S))$

见我的知乎文章

时间复杂度

参考文献

Pyton 代码

def solution():
    L = int(input())
    S, T, M = map(int, input().split())
    stones = sorted(map(int, input().split()))
    if S == T:
        print(sum(1 for e in stones if e % S == 0))
        return

    inf = float("inf")
    d = T * (T - 1)
    w = [0]
    for i in range(len(stones)):
        if i == 0:
            dist = min(stones[i], d)
        else:
            dist = min(stones[i] - stones[i - 1], d)
        w.extend([0] * dist)
        w[-1] = 1
    if L - stones[-1] > T:
        w.extend([0] * T)
    else:
        w.extend([0] * (L - stones[-1]))
    # print(w)
    dp = [inf] * len(w)
    dp[0] = 0
    # print(dp)

    for i in range(S, len(dp)):
        dp[i] = w[i] + min(dp[max(0, i - T) : i - S + 1])

    print(dp[-1])

solution()