SRM554 Div2 Hard(1000) TheBrickTowerHardDivTwo
TheBrickTowerHardDivTwo
動的計画法。高さ、上面のブロックの色、隣接した同色のブロックの個数ごとに、何通りの塔があるかを覚えておく。
class TheBrickTowerHardDivTwo{public: int find( int C, int K, int H ) { long long M = 1234567891; static long long T[47][4][4][4][4][8]; for ( int y=0; y<H; y++ ) for ( int c0=0; c0<C; c0++ ) for ( int c1=0; c1<C; c1++ ) for ( int c2=0; c2<C; c2++ ) for ( int c3=0; c3<C; c3++ ) { for ( int k=0; k<=K; k++ ) T[y][c0][c1][c2][c3][k] = 0LL; if ( y==0 ) { int t = int(c0==c1) + int(c1==c2) + int(c2==c3) + int(c3==c0); if ( t<=K ) T[y][c0][c1][c2][c3][t] = 1LL; } else { for ( int d0=0; d0<C; d0++ ) for ( int d1=0; d1<C; d1++ ) for ( int d2=0; d2<C; d2++ ) for ( int d3=0; d3<C; d3++ ) { int t = int(c0==c1) + int(c1==c2) + int(c2==c3) + int(c3==c0) + int(c0==d0) + int(c1==d1) + int(c2==d2) + int(c3==d3); for ( int k=0; k+t<=K; k++ ) T[y][c0][c1][c2][c3][k+t] += T[y-1][d0][d1][d2][d3][k], T[y][c0][c1][c2][c3][k+t] %= M; } } } long long ans = 0; for ( int y=0; y<H; y++ ) for ( int c0=0; c0<C; c0++ ) for ( int c1=0; c1<C; c1++ ) for ( int c2=0; c2<C; c2++ ) for ( int c3=0; c3<C; c3++ ) for ( int k=0; k<=K; k++ ) ans += T[y][c0][c1][c2][c3][k], ans %= M; return int(ans); }};