Codeforces Round #164

Problem D. Wall Bars

Brief description:

… 。。構造一個層數為 n 的塔。。每一層向四個方向中的一個伸出一個台階。。
。使得可以從地面登上塔頂。。攀爬的最大跨度為 h。。中間不可以換方向。
( n <= 1000, h <= 30 。。。

Analysis:

。。dp[i][x][y][z][w]:
。。O(n*h4) 狀態。。表示當前第 i 層。。四個方向的最後一塊木板距離當前層的距離分別為 x, y, z, w 時的方案數。。(。。當距離達到 h 時。。高度不再增加。此時的間隙已經過大。。之後不可以參與轉移。。
。。dp[i][x][y][z][w]:
。。O(n*h3) 狀態。。表示當前第 i 層。。上一層是否產生了不可轉移的間隙 w 。。。以及上上一層。。上上上 。的距離分別為分別 z, y, x 時的方案數。。(。。這樣狀態壓縮過後。。x,y,w,z 保存的都是相對位置。。
。。轉移依然是 O(1)。。枚舉四個方向。。。

http://codeforces.com/contest/268/submission/3032299

const int H = 30 + 1;
int dp[2][H][H][H][2];
int n, h;

int main(){

#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);
#endif

    while (scanf("%d %d", &n, &h) != EOF){
        int p = 0, q = 1; int _h = h; ++h; RST(dp[p]); dp[p][0][0][0][0] = 1;
        REP_1(i, n){
            swap(p, q); RST(dp[p]);
#define u dp[q][x][y][z][w]
#define t(x) (x==_h?_h:x+1)
#define ww(x) (x==_h)
            REP_4(x,y,z,w,h,h,h,2) if (u){
                int zz = w ? _h : 1;
                INC(dp[p][t(x)][t(y)][t(z)][w], u);
                INC(dp[p][t(x)][t(y)][zz][ww(z)], u);
                INC(dp[p][t(x)][t(z)][zz][ww(y)], u);
                INC(dp[p][t(y)][t(z)][zz][ww(x)], u);
            }
        }

        int res = 0; swap(p, q); REP_4(x,y,z,w,h,h,h,2) if (u){
            if (x<_h||y<_h||z<_h||!w) INC(res, u);
        }

        OT(res);
    }
}

External link:

http://codeforces.com/contest/268