AOJ 0568 Pasta
前の状態2つ考えないといけないと思ってたけど,1つで十分だった.
やっぱメモ化再帰のほうが何も考えずに書ける.
dp[i][j][k] := i日目にjのパスタをk個連続で作ったとき,i日目までの条件を満たす予定の数 n日目までの条件を満たす予定の数 ∋ i日目までの条件を満たす予定の数
ソースコード
const int MOD = 10000; int x[100]; int n, m; int dp[101][4][3]; int main() { int res = 0; cin >> n >> m; for(int i = 0, a, b; i < m; i++) { cin >> a >> b; x[a] = b; } if(x[1]) dp[1][x[1]][1] = 1; else for(int i = 1; i <= 3; i++) dp[1][i][1] = 1; for(int i = 2; i <= n; i++) if(x[i]) for(int j = 1; j <= 3; j++) if(x[i] == j) dp[i][j][2] += dp[i - 1][j][1] % MOD; else for(int k = 1; k < 3; k++) dp[i][x[i]][1] += dp[i - 1][j][k] % MOD; else // 今のパスタの種類 for(int j = 1; j <= 3; j++) // 1つ前のパスタの種類 for(int l = 1; l <= 3; l++) if(j == l) dp[i][j][2] += dp[i - 1][j][1] % MOD; else for(int k = 1; k < 3; k++) dp[i][j][1] += dp[i - 1][l][k] % MOD; for(int i = 1; i <= 3; i++) for(int j = 1; j < 3; j++) res += dp[n][i][j]; cout << res % MOD << endl; }