Codeforces #363 Div1 A. Vacations

この日SRMは-25ptでグダグダだったけど、Dが解けたおかげでCFは割とHighestに近づけた。
http://codeforces.com/contest/698/problem/A

問題

N日それぞれについて、ジム及びコンテストの利用可否が与えられる。
プレイヤーは各日について休む・ジムで運動する・コンテストに参加するのいずれかを選択できる。
ただしジムとコンテストは２日以上連続することができない。

最小で休む日を何日にできるか。

解法

典型的なDP。
dp(経過日数, 最後に行った動作) := その状態に致る休んだ日数の最小値
として状態を更新すればよい。

int N;
int A[101];
int dp[101][3];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	memset(dp,0x3f,sizeof(dp));
	dp[0][0]=0;
	cin>>N;
	
	FOR(i,N) {
		cin>>x;
		if(x&1) {
			dp[i+1][1]=min(dp[i+1][1],dp[i][0]);
			dp[i+1][1]=min(dp[i+1][1],dp[i][2]);
		}
		if(x&2) {
			dp[i+1][2]=min(dp[i+1][2],dp[i][0]);
			dp[i+1][2]=min(dp[i+1][2],dp[i][1]);
		}
		dp[i+1][0]=min(dp[i+1][0],dp[i][0]+1);
		dp[i+1][0]=min(dp[i+1][0],dp[i][1]+1);
		dp[i+1][0]=min(dp[i+1][0],dp[i][2]+1);
	}
	cout<<min(min(dp[N][0],dp[N][1]),dp[N][2])<<endl;
	
}

まとめ

いくらDiv1 Aとはいえヒネリが無さすぎるんだけど…。