SRM 484 div1 med: PuyoPuyo - mayoko’s diary

問題

解法

ある状態において, ぷよを全消しにするためにあと必要な最低限のぷよの個数を考えます。
例えば, 今の状態が RRBBR とかだったら, 全消しにするためには, RRBR とすれば良いので, この状態では必要なぷよの個数は 4 個です。これを用いて, dp[i][j] = (ぷよを i 個シリンダーに入れた状態で, 全消しにするために必要な最低限のぷよの数)とすると, j が 0 の時は, どの色のぷよを入れても全消しにするためのぷよは次に L-1 個必要になるので, dp[i+1][L-1] += 4*dp[i][0] となります。
他の場合は, 直前のぷよと同じ色を入れると, 全消しにするのに必要なぷよがひとつ減るので, dp[i+1][j-1] += dp[i][j] です。直前のぷよと別のぷよを入れると, 全消しにするのに必要なぷよは今までの分 + 新しく追加されたぷよを消すための L-1 個で, 結局 L-1 個増えるので, dp[i+1][j+L-1] += 3*dp[i][j] です。このような単純な dp で解けます。

const int MAXN = 1111;
const ll MOD = 1e9+7;
ll dp[MAXN][MAXN];

class PuyoPuyo {
public:
    int theCount(int L, int N) {
        memset(dp, 0, sizeof(dp));
        dp[0][0] = 1;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (j == 0) (dp[i+1][L-1] += dp[i][j]*4) %= MOD;
                else {
                    (dp[i+1][j-1] += dp[i][j]) %= MOD;
                    (dp[i+1][j+L-1] += dp[i][j]*3) %= MOD;
                }
            }
        }
        return (int)(dp[N][0]);
    }
};