PAST3H
from 第三回 アルゴリズム実技検定
PAST3H
H ハードルが置かれたコースを飛んだり飛ばなかったりして走る時の最短時間を求める。
地点xに至る最短時間を小さいxから順に求める。動的計画法
pythonif 1:
N, L = [int(x) for x in input().split()]
XS = [int(x) for x in input().split()]
T1, T2, T3 = [int(x) for x in input().split()]
if 0:
if 1:
L = 10
XS = []
T1, T2, T3 = 2, 2, 2
if 1:
L = 10
XS = []
T1, T2, T3 = 2, 4, 2
if 1:
L = 10
XS = []
T1, T2, T3 = 4, 2, 2
if 1:
L = 10
XS = [5]
T1, T2, T3 = 2, 4, 4
isHurdle = [False] * L
for x in XS:
isHurdle[x] = True
answer = 1e+99
# print(isHurdle)
def minUpdate(p, t):
# print("update?", p, t)
if p > L:
t = time + T1 // 2 + int((L - position - 0.5) * T2) + penalty
p = L
if fastestTimes[p] > t:
fastestTimes[p] = t
# print("updated")
fastestTimes = [1e+99] * (L + 1)
fastestTimes[0] = 0
for position in range(L):
time = fastestTimes[position]
penalty = T3 if isHurdle[position] else 0
minUpdate(position + 1, time + T1 + penalty)
minUpdate(position + 2, time + T1 + T2 + penalty)
minUpdate(position + 4, time + T1 + 3 * T2 + penalty)
# print(fastestTimes)
print(fastestTimes[L])Related Pages
- →abc168×第三回 アルゴリズム実技検定×abc169×abc173×僕のatcoderの学び方(〜緑)×arc106×僕のatcoderの学び方(〜水色)×abc183×abc187×僕のatcoderの学び方(〜青)→
- →僕のatcoderの学び方(〜緑)×僕のatcoderの学び方(〜青)×arc106×気づきの言語化×結晶化×変形テクニックに名前をつける×行列の半分×二項定理×足し算の順序の変更×概念のハンドル×テストできるスニペットライブラリ×unionfind×mod_pでの組み合わせ×Educational DP Contest×動的計画法×atcoder_library_practice_contest×atcoder_library×帰着する力×帰着訓練→
"Engineer's way of creating knowledge" the English version of my book is now available on [Engineer's way of creating knowledge]
(C)NISHIO Hirokazu / Converted from [Scrapbox] at [Edit]