AOJ 0568 - Pasta

典型的なDP問題．O(n)だと思います．

#include<iostream>

const int MAX_N = 100;
//memo[i][j][k]: i日目jをk+1日続けた総数
int memo[MAX_N+1][3][2], plan[MAX_N+1];

void pass(int day, int source){
	if(source != -1){
		memo[day][source][1] = memo[day-1][source][0];

		for(int j=0;j<3;j++){
			if(j != source){
				memo[day][source][0] += memo[day-1][j][0];
				memo[day][source][0] += memo[day-1][j][1];
				memo[day][source][0] %= 10000;
			}
		}
	}
}

int main(){
	int n, k;

	std::cin >> n >> k;

	std::fill(plan, plan+MAX_N+1, -1);

	for(int i=0;i<=MAX_N;i++){
		for(int j=0;j<3;j++){
			for(int k=0;k<2;k++){
				memo[i][j][k] = 0;
			}
		}
	}

	// a, b; a日目はbですよー
	for(int i=0;i<k;i++){
		int a, b;
		std::cin >> a >> b;
		plan[a] = b-1;
	}
	
	if(plan[1] != -1){
		memo[1][plan[1]][0] = 1;
	}else{
		memo[1][0][0] = 1;
		memo[1][1][0] = 1;
		memo[1][2][0] = 1;
	}

	for(int day=2;day<=n;day++){
		if(plan[day] != -1){//決まっている
			pass(day, plan[day]);
		}else{//決まっていない
			for(int source=0;source<3;source++){
				pass(day, source);
			}
		}
	}

	int res = 0;
	for(int i=0;i<3;i++){
		for(int j=0;j<2;j++){
			res += memo[n][i][j];
			res %= 10000;
		}
	}

	std::cout << res << std::endl;
}