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