Codeforces Round #363 Div.1 A. / Div.2 C. Vacations
*入力
*概要
日目のジムのオープン状況とコンテストの開催状況が、配列で与えられる。
ジム | コンテスト | その日の選択肢 | |
---|---|---|---|
× | × | 休む | |
× | ○ | 休む or コンテスト | |
○ | × | 休む or ジム | |
○ | ○ | 休む or コンテスト or ジム |
2日連続でジムへ行く、2日連続でコンテストに参加することはできない。
休む日は最小にしたい。
*解法
DPで解ける。
日目にを選んだとき日目までに休む日の最小値
は 休む
は コンテスト
は ジム
*出力
日目までに休む日の最小値。
つまり
のうちの最小値。
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]))