poj 2411 Mondriaan's Dream 状压DP

缘起

日常浪费生命~ poj 2411 Mondriaan’s Dream

分析

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
Description
有一个W行H列的棋盘，你可以在里放1*2的骨牌，骨牌之间互相不重叠，问放满整个棋盘有多少种方案数。

Input
输入文件有多组数据，每组数据只有一行为两个整数W和H(1<=W,H<=11)。

Output
每组数据一行为方案总数，若不能够放满整个棋盘输出0。

Sample Input
1 2 
1 3 
1 4
2 2
2 3
2 4
2 11
4 11

Sample Output
1
0
1
2
3
5
144
51205

限制
3s

w和h都比较小. 所以考虑状压dp. 看下面的图示. 本题的核心思想就是从左至右、从上至下逐一填写格子的时候（反正每个格子你总要覆盖的嘛~）,只需要注意到下图中只有深色格子部分是是否被覆盖的情况不确定的. 浅色格子的覆盖情况是确定了的（偏下的浅色格子是一定没被覆盖的，偏上的浅色格子是一定被覆盖了的）. 而深色格子的数量是w. 而w<=11, 所以可以使用二进制压缩w个格子被覆盖的所有情况(<=2048种情况).

令

1
2
3
4
5
6
7
dp[i][j][k]是i行j列的格子,深色格子的状态是k的时候, 剩余格子覆盖的方法数.
则 0<=k<2^w. 
显然有dp初始值
dp[h-1][w-1][0]=0（因为骨牌是1*2的, 所以你只剩下一个格子没填的话, 则是无法继续填一块骨牌的）
dp[h-1][w-1][1]=0 (因为已经填满了, 所以方法数就是1)
然后按照当前格子是否填了, 分情况讨论（即横着放或者竖着放, 及时更新k的值即可），
具体dp的过程参见下面的ac代码就可以了

代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
//#include "stdafx.h"

#include <stdio.h>
#include <string.h>
//#define LOCAL
typedef long long LL;

LL w,h, dp[15][15][2100]; // dp的规模是10w, 不需要滚动优化~

bool nxt(LL i, LL j, LL &ni, LL &nj) // 判断当前格子(i,j)有没有下一个位置(所谓下一个~ 顺序是从上至下, 从左至右)
{
	if (i==h-1&&j==w-1)
	{
		return false;
	}
	nj = (j+1)%w;
	ni = nj?i:(i+1); // 是0的话就表示跑到下一行去了
	return true;
}

int main()
{
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
#endif
	while(~scanf("%lld%lld", &w ,&h), w||h)
	{
		memset(dp, 0, sizeof(dp));
		dp[h-1][w-1][0] = 0, dp[h-1][w-1][1] = 1; // 初始化
		for (LL i = h-1; i>=0; i--)
		{
			for (LL j = w-1,ni,nj; j>=0; j--)  // 考察(i,j)处的格子, 按照从左至右、从上至下的顺序填格子
			{
				for (LL k = 0; k<(1<<w); k++) // 考察状态k
				{
					bool hasnxt = nxt(i,j,ni,nj); // 是否有下一个格子, 如果有的话, (ni,nj)是下一个格子
					if (k&1) // 如果当前格子已经填了
					{
						if (hasnxt) // 如果有下一个格子
						{
							dp[i][j][k] = dp[ni][nj][k>>1];
						}
					}
					else // 如果当前格子没有填, 则就要区分竖着放还是横着放
					{
						if (i+1<h) // 如果可以竖着放, 注意, 如果i+1<h的话, 则看图就知道当前格子的下面的那个格子是一定没填的
						{
							dp[i][j][k]+=dp[ni][nj][(k>>1) | (1<<w-1)]; // 自己比划一下就知道下一个状态是(k>>1)+(1<<w-1) 了
						}
						if (j+1<w && !(k&2)) // 如果可以横着放
						{
							dp[i][j][k] += dp[ni][nj][(k|2)>>1]; // 自己比划一下就知道下一个状态是 (k+2)>>1
						}
					}
				}
			}
		}
		printf("%lld\n", dp[0][0][0]);
	}
	return 0;
}

ac情况

Status Accepted
Time 454ms
Memory 3832kB
Length 1286
Lang C++
Submitted 2019-09-19 17:15:12
RemoteRunId 20875489