AOJ 0568 Pasta

JOI予選のとき、動的計画法ということには気づいたけど頭悪いのでどうすればよいか分からなかった問題。
教訓：とりあえず再帰関数
問題
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0568
解法
動的計画法またはメモ化再帰をつかう。
メモ化再帰のほうが楽です。

#include <cstdio>
#include <algorithm>
using namespace std;

const int MAX_N = 100;
int N, K;
int plan[MAX_N + 1];
int memo[MAX_N + 1][4][4];
int solve(int n, int b1, int b2){
	if(n == N+1) return 1;
	if(memo[n][b1][b2] != -1) return memo[n][b1][b2];
	if(plan[n] != 0){
		if(b1 == b2 && b1 == plan[n])
			return 0;
		else
			return solve(n+1, plan[n], b1)%10000;
	}
	int t=0;
	for(int i=1; i<=3; ++i){
		if(b1==b2 && b1==i ) continue;
		t+=solve(n+1, i, b1)%10000;
	}
	return memo[n][b1][b2] = t%10000;
}
int main(){
	scanf("%d %d", &N, &K);
	for(int i=0; i<K; ++i){
		int d, k;
		scanf("%d %d", &d, &k);
		plan[d] = k;
	}
	for(int i=0; i<=N; ++i)
		for(int j=0; j<4; ++j)
			for(int k=0; k<4; ++k)
				memo[i][j][k] = -1;
	printf("%d\n", solve(1, 0, 0));
	return 0;
}