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;
}