読者です 読者をやめる 読者になる 読者になる

Codeforces Round #363 Div.1 A. / Div.2 C. Vacations

*問題文
Problem - C - Codeforces

*入力
n
a_1, a_2, …, a_n

*概要
i 日目のジムのオープン状況とコンテストの開催状況が、配列aで与えられる。

a_i ジム コンテスト その日の選択肢
0 × × 休む
1 × 休む or コンテスト
2 × 休む or ジム
3 休む or コンテスト or ジム

2日連続でジムへ行く、2日連続でコンテストに参加することはできない。
休む日は最小にしたい。

*解法
DPで解ける。
dp [ i日目に] [ jを選んだとき]  := i日目までに休む日の最小値

j=0 は 休む
j=1 は コンテスト
j=2 は ジム

*出力
n日目までに休む日の最小値。
つまり
dp [ n ] [ 0 ],dp [ n ] [ 1 ],dp [ n ] [ 2 ] のうちの最小値。

ソースコード

n = int(input())
a = list(map(int,input().split()))

dp = [[10**10] * 3 for i in range(n+1)]
dp[0][0] = 0
dp[0][1] = 0
dp[0][2] = 0

for i in range(1, n+1):
    if a[i-1] == 0:
        dp[i][0] = min(dp[i-1][0], dp[i-1][1], dp[i-1][2]) + 1
    elif a[i-1] == 1:
        dp[i][0] = min(dp[i-1][0], dp[i-1][1], dp[i-1][2]) + 1
        dp[i][1] = min(dp[i-1][0], dp[i-1][2])
    elif a[i-1] == 2:
        dp[i][0] = min(dp[i-1][0], dp[i-1][1], dp[i-1][2]) + 1
        dp[i][2] = min(dp[i-1][0], dp[i-1][1])
    else:
        dp[i][0] = min(dp[i-1][0], dp[i-1][1], dp[i-1][2]) + 1
        dp[i][1] = min(dp[i-1][0], dp[i-1][2])
        dp[i][2] = min(dp[i-1][0], dp[i-1][1])

print(min(dp[n][0], dp[n][1], dp[n][2]))