AOJ 0568 Pasta

競プロ
  • 概要

日本語問題なので省略させていただきます。

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0568

  • 解法

動的計画法

dp[i][j][k] i日目のパスタがj。i+1日目のパスタがkのときのパターン数

その日のパスタがtの場合にはdp[i][t][1〜3]のみを更新する。

あんまり難しくないんですが、自分みたいに書くとiとかjとか間違えて死ぬ

#include<cstdio>
using namespace std;
int p[100];
long long int dp[100][3][3];
int main()
{
	int n,k;
	long long int sum=0;
	scanf("%d%d",&n,&k);

	for(int i=0;i<k;i++){
		int a,b;
		scanf("%d%d",&a,&b);
		p[a-1]=b;
	}

	if(p[0]){
		for(int i=0;i<3;i++){
			dp[0][p[0]-1][i]=1;
		}
	}else{
		for(int i=0;i<3;i++){
			for(int j=0;j<3;j++){
				dp[0][i][j]=1;
			}
		}
	}

	for(int i=1;i<n;i++){
		if(p[i]==1){
			dp[i][0][0]+=(dp[i-1][1][0]+dp[i-1][2][0])%10000;
			for(int j=0;j<3;j++){
				dp[i][0][1]=(dp[i-1][j][0]+dp[i][0][1])%10000;
				dp[i][0][2]=(dp[i-1][j][0]+dp[i][0][2])%10000;
			}
		}else if(p[i]==2){
			dp[i][1][1]+=(dp[i-1][0][1]+dp[i-1][2][1])%10000;
			for(int j=0;j<3;j++){
				dp[i][1][0]=(dp[i-1][j][1]+dp[i][1][0])%10000;
				dp[i][1][2]=(dp[i-1][j][1]+dp[i][1][2])%10000;
			}
		}else if(p[i]==3){
			dp[i][2][2]+=(dp[i-1][0][2]+dp[i-1][1][2])%10000;
			for(int j=0;j<3;j++){
				dp[i][2][0]=(dp[i-1][j][2]+dp[i][2][0])%10000;
				dp[i][2][1]=(dp[i-1][j][2]+dp[i][2][1])%10000;
			}
		}else{
			dp[i][0][0]+=(dp[i-1][1][0]+dp[i-1][2][0])%10000;
			dp[i][1][1]+=(dp[i-1][0][1]+dp[i-1][2][1])%10000;
			dp[i][2][2]+=(dp[i-1][0][2]+dp[i-1][1][2])%10000;

			for(int j=0;j<3;j++){
				dp[i][0][1]=(dp[i-1][j][0]+dp[i][0][1])%10000;
				dp[i][0][2]=(dp[i-1][j][0]+dp[i][0][2])%10000;
				dp[i][1][0]=(dp[i-1][j][1]+dp[i][1][0])%10000;
				dp[i][1][2]=(dp[i-1][j][1]+dp[i][1][2])%10000;
				dp[i][2][0]=(dp[i-1][j][2]+dp[i][2][0])%10000;
				dp[i][2][1]=(dp[i-1][j][2]+dp[i][2][1])%10000;
			}
		}
	}
	for(int i=0;i<3;i++){
		for(int j=0;j<3;j++){
			if(p[n-1] && p[n-1]-1!=j)continue;
			sum=(sum+dp[n-2][i][j])%10000;
		}
	}
	printf("%lld\n",sum);
	return 0;
}