Hatena::Grouptopcoder

chokudaiの日記

 | 

2010-10-19

SRM484 Div1 Medium PuyoPuyo

04:50 | SRM484 Div1 Medium PuyoPuyo - chokudaiの日記 を含むブックマーク はてなブックマーク - SRM484 Div1 Medium PuyoPuyo - chokudaiの日記 SRM484 Div1 Medium PuyoPuyo - chokudaiの日記 のブックマークコメント

問題

問題概要:盤面が幅1の盤面に1個ずつぷよぷよ(4色)がN個降ってきてL個で消える.全消しパターンは何通り?

N<1000, 2<L<10</ppp>

解法

動的計画法により解く!

メモするのは、「今までにいくつぷよぷよを降らせたか」「消えてないぷよぷよはいくつか」「以前ぷよぷよが消えてから、余ってしまうぷよぷよを置いたかどうかのフラグ」の3つ。それぞれ最大、N,N,2個となる

それぞれに対して、

  • 「L個いきなり置いて消してしまう(フラグは1となる)」
  • 「L-K個の不完全なぷよを配置する(フラグが0となる)」
  • 「1個、不完全なぷよを補充する(フラグが1の時限定)」

の3つの処理を順番に行って値を更新すれば答えが求まります!

public class PuyoPuyo {

    const long mod = 1000000007;
    const int MAX = 1024;
    long[,,] dp = new long[MAX, MAX, 2]; //おいた数、消さないといけないのの数
    public int theCount(int L, int N)
    {
        int i, j, k, l;
        for (i = 0; i < MAX; i++)
        {
            for (j = 0; j < MAX; j++)
            {
                for (l = 0; l < 2; l++)
                {
                    dp[i, j, l] = 0;
                }
            }
        }
        dp[0, 0, 1] = 1;
        for (i = 0; i <= N; i++)
        {
            for (j = 0; j <= N; j++)
            {
                for (l = 0; l < 2; l++)
                {
                    if (dp[i, j, l] == 0) continue;
                    //Console.WriteLine(i + " " + j + " " + dp[i, j]);
                    int kakeru = 3;
                    if (j == 0) kakeru = 4;

                    dp[i + L, j, 1] += dp[i, j, l] * kakeru;

                    for (k = 1; k < L; k++)
                    {
                        dp[i + k, j + L - k, 0] += dp[i, j, l] * kakeru;
                        dp[i + k, j + L - k, 0] %= mod;
                    }
                    if (j != 0 && l == 1)
                    {
                        dp[i + 1, j - 1, l] += dp[i, j, l];
                        dp[i + 1, j - 1, l] %= mod;
                    }
                }
            }
        }

        return (int)((dp[N, 0, 0] + dp[N, 0, 1]) % mod);
    }

}

ゲスト



トラックバック - http://topcoder.g.hatena.ne.jp/chokudai/20101019
 |