SRM523 Div1 Medium(500) BricksN

BricksN

動的計画法。幅iのブロックの上に高さが高々jになるようにブロックを積む場合の数を覚えておく。全くブロックを積まない場合が１通り。あとは最左のブロックの固まりを置く場所ごとに、ブロックの固まりの作り方×上の積み上げ方×１つ隙間を空けて右のブロックの固まりの置き方　を足し合わせる。長さiになるように隙間無くブロックを並べる場合の数は予め求めておく。

#include <string>
#include <vector>

using namespace std;

class BricksN{public:
int countStructures( int w, int h, int k )
{
    long long M = 1000000007;

    //  [i]: 幅iに隙間無くブロックを置く場合の数
    vector<long long> T1( w+1 );
    T1[0] = 1;
    for ( int x=1; x<=w; x++ )
        for ( int i=1; i<=min(k,x); i++ )
            T1[x] += T1[x-i],  T1[x] %= M;

    //  [i][j]: 幅jのブロック上に高さが高々iになるようにブロックを置く場合の数
    vector<vector<long long> > T2( h+1, vector<long long>(w+1) );
    for ( int x=0; x<=w; x++ )
        T2[0][x] = 1;
    for ( int y=1; y<=h; y++ )
    {
        T2[y][0] = 1;
        for ( int x=1; x<=w; x++ )
        {
            T2[y][x] = 1;
            for ( int i=0; i<x; i++ )
            for ( int j=i+1; j<=x; j++ )
            {
                long long t = 1;
                t *= T1[j-i],  t %= M;
                t *= T2[y-1][j-i],  t %= M;
                if ( x-j-1>=1 )
                    t *= T2[y][x-j-1],  t %= M;
                T2[y][x] += t,  T2[y][x] %= M;
            }
        }
    }

    return (int)T2[h][w];
}};