Vacations [Codeforces 363 : Div2 C, Div1 A]

問題

http://codeforces.com/contest/698/problem/A

n個の数列aiがある。
aiはその日の状況を表しており、

• ai = 0 : ジム閉まってる。コンテストやってない
• ai = 1 : ジム閉まってる。コンテストやってる
• ai = 2 : ジム開いてる。コンテストやってない
• ai = 3 : ジム開いてる。コンテストやってる

ジムが開いていれば運動できるし、コンテストやってれば参加できる。
２日続けて、運動・コンテスト参加はしない。
この時、運動・コンテスト参加をしていない（休憩してる）日は最小で何日にできるか。

1 <= n <= 100

考察

1. nの数が極端に少ない！（俺が考えついた解法では使わなかった）
2. 全探索するとO(4^n)
3. 減らしたい！多項式時間にしたい！
4. 指数時間を多項式時間 -> DPかな？

5. DPで考えればできます

dp[i][j] = i日目で最後が...
j = 0 休憩した
j = 1 コンテスト参加した
j = 2 運動した
時の休憩した日の最小日

実装

http://codeforces.com/contest/698/submission/19257794

int n;
int dp[101][3];
//-----------------------------------------------------------------
#define INF INT_MAX/2
int main() {
	cin >> n;

	rep(i, 0, n + 1) rep(j, 0, 3) dp[i][j] = INF;
	dp[0][0] = 0;
	rep(i, 0, n) {
		int a; scanf("%d", &a);

		dp[i + 1][0] = min(dp[i][0] + 1, min(dp[i][1] + 1, dp[i][2] + 1));
		if (a % 2 == 1) dp[i + 1][1] = min(dp[i][0],dp[i][2]);
		if (2 <= a) dp[i + 1][2] = min(dp[i][0], dp[i][1]);
	}
	int ans = min(dp[n][0], min(dp[n][1], dp[n][2]));
	cout << ans << endl;
}