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);    
}};