SRM523 Div2 Hard(1000) SmallBricks31

SmallBricks31

動的計画法。下から順にブロックを積んでいき、現在のx,y座標と上に出ているブロックの配置ごとにパターン数を覚えておく。

#include <vector>
using namespace std;

int M = 1000000007;
int w, h;
vector<int> B;
vector<vector<vector<int> > > memo;

int BT( int x, int y )
{
    if ( y > h )
        return 1;
    if ( x >= w )
        return BT(0,y+1);

    int b = B[y-1]>>x<<x | B[y]&((1<<x)-1);
    if ( memo[x][y][b] >= 0 )
        return memo[x][y][b];
    
    long long ans = 0;

    ans += BT(x+1,y);
    ans %= M;

    for ( int i=1; i<=3; i++ )
    if ( x+i-1<w && B[y-1]>>x&1 && B[y-1]>>(x+i-1)&1 )
    {
        for ( int j=0; j<i; j++ )
            B[y] ^= 1<<(x+j);

        ans += BT(x+i,y);
        ans %= M;

        for ( int j=0; j<i; j++ )
            B[y] ^= 1<<(x+j);
    }

    return memo[x][y][b] = (int)ans;
}

class SmallBricks31{public:
int countWays( int w, int h )
{
    ::w = w;
    ::h = h;
    B = vector<int>( h+1 );
    B[0] = (1<<w)-1;
    memo = vector<vector<vector<int> > >( w, vector<vector<int> >( h+1, vector<int>(1<<w,-1) ) );

    return BT( 0, 1 );  
}};