AtCoder Beginner Contest 040 C – 柱柱柱柱柱 をPython3で解く

# AtCoder Beginner Contest 040 C - 柱柱柱柱柱
# https://atcoder.jp/contests/abc040/tasks/abc040_c
# tag: DP 典型問題 基礎問題 高橋君

# 典型的かつ基礎的なDPで解ける問題。
# dp_table[i] = i+1 番目の柱に行くための最小コスト
# として、スタート地点から順に更新していく
# i+1 番目としているのは、0-indexed でテーブルを作成するからで、
# それ以上の意味はない。（1 番目の柱に行くコスト = dp_table[0] = 0）

# この DP が成立するのは、各移動を独立して考えることが可能なため。
# つまり、過去にどのような経路を通って移動したかが問われないので、
# i 番目の柱にコスト c で到達できた場合、その結果のみで
# 計算結果をまとめることが出来る。

# 逆に今回の DP が使えないケースを考えてみると、
# 例えば2回連続で2個先の柱に飛ぶ時は（疲れるので）コストが x 増える
# みたいな場合には、前回の行動を組み込む必要があるため、
# まとめ方が変わる ＝ 違ったDPを使う必要がある。
# 具体的には、さらに場合を分けて
# dp_table[i][prev] = i+1 番目の柱に前回 prev+1 歩進んだ時のコスト
# みたいな感じで行うことになる……はず？

def main():
    N = int(input())
    pillars = list(map(int, input().split()))

    # dp用テーブル（名前を dp とする人が多いけど、個人的には dpt）
    dpt = [10**10] * N

    # 最初の柱はコスト 0 なので、設定しておく
    dpt[0] = 0

    # いわゆる配るDPで、わかりやすいように
    # やや回りくどく書いていくと……
    for now in range(N-1):
        # 次の柱に飛ぶ場合
        next_p = now + 1

        # トータルのコストを計算し、最小値に更新する
        cost = dpt[now] + abs(pillars[next_p] - pillars[now])
        dpt[next_p] = min(dpt[next_p], cost)

        # 二個先の柱に飛ぶ場合
        next_next_p = now + 2

        # 行き過ぎる時は計算しない
        if next_next_p >= N:
            continue

        # トータルのコストを計算し、最小値に更新する
        cost = dpt[now] + abs(pillars[next_next_p] - pillars[now])
        dpt[next_next_p] = min(dpt[next_next_p], cost)
    
    print(dpt[-1])

main()

# ついでに、もらうDPでも……
def main2():
    N = int(input())
    pillars = list(map(int, input().split()))

    dpt = [10**10] * N
    dpt[0] = 0

    for now in range(1, N):
        prev_p = now - 1
        cost = dpt[prev_p] + abs(pillars[now] - pillars[prev_p])
        dpt[now] = min(dpt[now], cost)

        prev_prev_p = now - 2
        if prev_prev_p < 0:
            continue
        cost = dpt[prev_prev_p] + abs(pillars[now] - pillars[prev_prev_p])
        dpt[now] = min(dpt[now], cost)
    
    print(dpt[-1])

# main2()

# せっかくなのでメモ化再帰でも
# 再帰の深さ制限を解除しておかないとREになるので注意
import sys
sys.setrecursionlimit(10**9)
def main3():
    N = int(input())
    pillars = list(map(int, input().split()))

    memo = [-1] * N
    memo[0] = 0

    def get_min_cost(pos):
        if memo[pos] != -1:
            return memo[pos]

        cost = get_min_cost(pos - 1) + abs(pillars[pos-1] - pillars[pos])

        if pos > 1:
            cost = min(cost, get_min_cost(pos-2) + abs(pillars[pos-2] - pillars[pos]))

        memo[pos] = cost

        return cost
    
    print(get_min_cost(N-1))

# main3()