みんなのプロコン 2019 D

問題

解けなかった。

解答PDFを参考にすると、

となるので、配列をDPで更新していけば解けることが分かる。

import sys
readline = sys.stdin.readline
L = int(input())
dp = [0] * 5
for a in map(int, (readline() for _ in range(L))):
    back = a % 2 if a > 0 else 2
    through = (a + 1) % 2
    dp[4] = min(dp[:5]) + a
    dp[3] = min(dp[:4]) + back
    dp[2] = min(dp[:3]) + through
    dp[1] = min(dp[:2]) + back
    dp[0] += a
print(min(dp))