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