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

Posted by xiaodao
Category: Codeforces