noi.ac #43 dp计数

(sol)
状态

[f_{i, dis_1, dis_2, dis_3, dis_4} ]

表示到了第 (i) 层，其中 (dis_{1}) 表示第一根柱子剩下的最靠上的横木到当前 (i) 层的距离，以此类推。
显然后四维的范围 ([0, h])
枚举这一层所留下的横木是在哪一个梯子上，对应的 (dis) 变为 (0), 如果 (dis) 为 (h)，说明已经断了，这种情况还是 (h), 其他的 (dis + 1) 如果已经是 (h) 则不变
时间复杂度 (O(nh^4))

由于每一层必定会存在一个横木，也就是必定会有一个梯子 (dis) 为 (0)
所以了以减少以为的 (dis)
同时改为 (0/1) 记录这一个梯子是否能不断连接到当前行。

[f_{i, 0/1, dis_{2}, dis_{3}, dis_{4}} ]

表示到了 (i) 层，在这一层放横木的那个梯子是否能爬到当前层，(dis) 同理

时间复杂度 (O(nh^3))
滚动数组优化空间

(cod)

#include<cstdio>
#include<cmath>
#include<cstdlib>
#include <algorithm>
#include <cstring>
#include <queue>

using namespace std;
const int mod = 1e9 + 9;

int n, h;

int now, old;
int f[2][2][33][33][33];

#define nex(x) ((x) == h ? h :(x) + 1)

void MOD(int &x)  {
	if (x >= mod) x -= mod;
}

int main() {
	
	scanf("%d%d", &n, &h);
	
	old = 0, now = 1;
	f[old][1][0][0][0] = 1;
	
	int tmp;
	for (int i = 1; i <= n; i ++) {
		for (int j = 0; j <= 1; j ++)
			for (int x = 0; x <= h; x ++)
				for (int y = 0; y <= h; y ++)
					for (int z = 0; z <= h; z ++)
					if (tmp = f[old][j][x][y][z]) {
						MOD(f[now][j][nex(x)][nex(y)][nex(z)] += tmp);
						MOD(f[now][x < h][nex(y)][nex(z)][j == 1 ? 1 : h] += tmp);
						MOD(f[now][y < h][nex(x)][nex(z)][j == 1 ? 1 : h] += tmp);
						MOD(f[now][z < h][nex(x)][nex(y)][j == 1 ? 1 : h] += tmp);
						f[old][j][x][y][z] = 0;
					}
		swap(now, old);
	}
	
	int ans = 0;
	for (int j = 0; j <= 1; j ++)
		for (int x = 0; x <= h; x ++)
			for (int y = 0; y <= h; y ++)
				for (int z = 0; z <= h; z ++) 
				if (j == 1 || x < h || y < h || z < h)
					ans += f[old][j][x][y][z], MOD(ans);
	printf("%d", ans);
	return 0;
}