SRM523 Div2 Hard(1000) 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 ); }};