EDPC A - Frog 1

AtCoder Python3 動的計画法

備忘録

問題

atcoder.jp

回答

import sys

sys.setrecursionlimit(10000000)
import os
import math
import bisect
import collections
import itertools
import heapq
import re
import queue

# import fractions

ii = lambda: int(sys.stdin.buffer.readline().rstrip())
il = lambda: list(map(int, sys.stdin.buffer.readline().split()))
fl = lambda: list(map(float, sys.stdin.buffer.readline().split()))
iln = lambda n: [int(sys.stdin.buffer.readline().rstrip()) for _ in range(n)]

iss = lambda: sys.stdin.buffer.readline().decode().rstrip()
sl = lambda: list(map(str, sys.stdin.buffer.readline().decode().split()))
isn = lambda n: [sys.stdin.buffer.readline().decode().rstrip() for _ in range(n)]

lcm = lambda x, y: (x * y) // math.gcd(x, y)
# lcm = lambda x, y: (x * y) // fractions.gcd(x, y)

MOD = 10 ** 9 + 7
MAX = float('inf')


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    N = ii()
    H = il()

    dp = [0]*N
    dp[1] = abs(H[0]-H[1])
    for n in range(2, N):
        dp[n] = min(abs(H[n-2]-H[n])+dp[n-2], abs(H[n-1]-H[n])+dp[n-1])
    print(dp[-1])


if __name__ == '__main__':
    main()

考え方

動的計画法を用いて、一つまたは二つ移動する場合を全てシミュレーションし、
常に最もコストが小さい移動を採用する。

足場１はカエルの初期位置なので、移動コストは0
足場２は足場１から+1の移動方法しか存在しないため、
コストはabs(足場１の高さ - 足場２の高さ)となる。

足場３は足場１または足場２から移動することができる。
この時、足場３への移動コストは

  • 足場１から移動した場合 = abs(足場１の高さ - 足場３の高さ）+ 足場１までの移動コスト
  • 足場２から移動した場合 = abs(足場２の高さ - 足場３の高さ) + 足場２までの移動コスト

の2択となり、小さいほうを移動に採用する。

上記の処理を足場の数だけ行い、
常にコストが小さい移動を採用することで終点まで移動するコストの最小値を求めることができる。