题解 | #[NOIP2005]过河#
[NOIP2005]过河
https://ac.nowcoder.com/acm/problem/16655
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)