2016-07-20

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

＊入力
$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]))