题解 | #[NOIP2005]过河#

python 解答

if __name__ == "__main__":
    # L = 100
    # S, T, M = 2, 3, 5
    # stone_pos = [0, 2, 3, 5, 11,12,13,15, L]

    L = int(input()) # 桥长度
    S,T,M = map(int,input().split()) # S T代表跳跃区间，M代表石头个数
    stone_pos = list(map(int,input().split())) # stone_pos代表位置
    # 对石头位置进行排序
    stone_pos = sorted(stone_pos)
    # 添加0位置和最后的一个位置
    stone_pos = [0] + stone_pos + [L]
    v = [0] * 2005
    cnt = 0
    # 缩短石头距离
    for i in range(1,M+2):
        if stone_pos[i] - stone_pos[i-1] > T:
            # 取模后再+T
            cnt += (stone_pos[i] - stone_pos[i-1]) % T + T
        else:
            cnt += stone_pos[i] - stone_pos[i - 1]
        # 新的石头位置
        v[cnt] = 1
    # 对于最后石头设置为0，初始位置也为0
    v[cnt] = 0
    v[0] = 0
    # init 初始值为最大
    dp = [sys.maxsize] * 2005
    # 0位置为0
    dp[0] = 0
    # 遍历从1开始，然后遍历到跳到最大位置即 cnt + T
    for i in range(1,cnt+T+1):
        # 遍历 j 必须在ST之间，
        for j in range(S,T+1):
            # 当i-j大于0，那么满足跳条件
            if i - j >= 0:
                # dp[i]依赖dpi-j],并且当v[i]有石头就+1，没有+0
                dp[i] = min(dp[i],dp[i-j] + v[i])
    res = sys.maxsize
    # 最后因为重要跳出来就行，因此找到cnt之后的最小值
    for i in range(cnt,cnt+T+1):
        res = min(res,dp[i])
    print(res)