AOJ0568 パスタ

JOI予選問題

解法:典型的なDP
問題しっかり読もうと思った

#include <cstdio>

using namespace std;

int main(){

	const int mod = 10000;
	
	int n,k;
	
	int yotei[102]={0};
	
	int dp[102][4][2] = {0};
	
	
	scanf("%d%d",&n,&k);
	
	for(int i = 0;i < k;i++){
		int a,b;
		
		scanf("%d%d",&a,&b);
		
		yotei[a] = b;
		
	}
	
	if(yotei[1] != 0){
		
		
		dp[1][yotei[1]][0] = 1;
		
	}else{
		
		for(int j = 1;j <= 3;j++){
			dp[1][j][0] = 1;
		}
	}
	
	
	for(int i = 2;i <= n;i++){
	
		int sum0=0,sum1=0;
		
		for(int j = 1;j <= 3;j++){
			
			sum0 += dp[i-1][j][0];
			sum1 += dp[i-1][j][1];
		}
		
	
		
		if(yotei[i] != 0){
			
			dp[i][yotei[i]][0] += (sum0 + sum1 - dp[i-1][yotei[i]][0] - dp[i-1][yotei[i]][1])%mod;
			dp[i][yotei[i]][1] += (dp[i-1][yotei[i]][0])%mod;
			
		}else{
			
			for(int j = 1;j <= 3;j++){
				
				dp[i][j][0] += (sum0 + sum1 - dp[i-1][j][0] - dp[i-1][j][1])%mod;
				dp[i][j][1] += (dp[i-1][j][0])%mod;
			}
			
		}
		
	}
	
	int ans = 0;
	
	for(int i = 1;i <= 3;i++){
	ans += (dp[n][i][0] + dp[n][i][1] )%mod;
	}
	
	ans %= mod;
	
	printf("%d\n",ans);
	
	return 0;
	
}