ABC251 E - Tahakashi and Animals

atcoder.jp

iを1～Nとして、動物iを押さえたときに、用いた行動が、0：iなのか、1：i-1なのか、の2状態を持ち、それぞれの最小コストを更新するようなDPを持つ（苦手なので日本語が微妙…）
ここで、動物2に対して行動2(i)、動物3に対して行動2(i-1)のような選択は意味がないため、コスト0の遷移とする。
また、初期値、すなわち動物1を押さえたのは、行動1なのか、行動Nなのか、うまく表現できないので、このセットをもう一つ持つことにする。 （0→2　1→3に対応） 初期値に行動Nを取り入れている場合、動物Nは気にしなくてよいため、N-1（-2番目）を参照する。そうでない場合は、Nを気にするので、N（-1番目）を参照する。

def resolve():
    N = int(input())
    A = list(map(int, input().split()))

    INF = 10 ** 20
    DP = [[INF] * N for i in range(4)]

    DP[0][0] = A[0]
    DP[3][0] = A[-1]

    for i in range(1, N):
        DP[0][i] = min(DP[0][i], DP[0][i - 1] + A[i])
        DP[0][i] = min(DP[0][i], DP[1][i - 1] + A[i])
        DP[1][i] = min(DP[1][i], DP[0][i - 1])
        DP[1][i] = min(DP[1][i], DP[1][i - 1] + A[i - 1])
        DP[2][i] = min(DP[2][i], DP[2][i - 1] + A[i])
        DP[2][i] = min(DP[2][i], DP[3][i - 1] + A[i])
        DP[3][i] = min(DP[3][i], DP[2][i - 1])
        DP[3][i] = min(DP[3][i], DP[3][i - 1] + A[i - 1])

    print(min(DP[0][-1], DP[1][-1], DP[2][-2], DP[3][-2]))


resolve()