POJ2411-铺地砖计数题解-状压DP教学

|

http://poj.org/problem?id=2411

题解 Solution

好久不写题了，昨晚学长突然问我这个问题做出来还花了不少时间

看到这题第一个想法是搞出一个计数公式，发现毫无头绪。再仔细想想感觉这种问题有一点印象，也许可以通过递推之类的得到结果。这时就想到了使用动态规划，我们可以逐行逐行地进行状态转移来计算总的方案数，也就是说如果我们知道了填满前 $n-1$ 行的方案数，我们可以递推出填满前 $n$ 行的答案。

那么怎么进行状态转移呢？

假设现在我们要从第 $n-1$ 行递推到第 $n$ 行，我们不妨用$1$表示在这里竖放了一枚砖块(且$1$表示是竖放砖块的上端)，那么第$n-1$行砖块的状态可以用一个$01$数组表示，比如一个列数为$5$的例子:

第一个$0$说明它是一个竖放砖块的下端，第$2$和第$3$个$1$表示它们两个分别都是一个竖放砖块的上端，而后面两个$0$有两种情况，它们既可能表示一枚横放的砖块，也有可能是两个竖放砖块的下端

继续拿这个例子说话，我们既然已经知道了第$n-1$行砖块放置的情况，那么我们就知道了哪些状态是它能够状态转移到第$n$行的, 也就是说哪些第$n$行的砖块放置状态是它能够合法地转移过来的。

以下是$01100$所有能够合法转移的状态:

这里是解释，对于第 $n-1$ 行的第一个$0$，由于下一行无法从第一列开始横着放（因为第二列必须是竖着放的下端），所以第 $n$ 行的第一列一定是$1$；对于第二列和第三列，由于在第 $n-1$ 行它们是两块竖放砖块的上端，所以第 $n$ 行的第二列和第三列必须是 $0$；而对于第$n-1$行第四列和第五列的$0$, 第 $n$ 行既可以是两块竖放砖块的上端，也可以是一块横着放的砖块。

如果你看懂了这些，不难归纳出状态转移的合法标准:

  • $1$ 的对应状态是 $0$
  • $0$ 的对应状态是 $1$; 但是 $0 0$ 的对应状态可以是 $00$

在动态规划的状态转移中，如果我们枚举每一个状态都用 $01$ 数组表示也太麻烦了，所以干脆就用一个数的二进制形式来表示这个 $01$ 数组 ，也就是状态压缩的技巧。所以称之为状态压缩动态规划 (abbr. 状压DP)

既然是二进制表示，就需要了解基本的位运算符号和一些基本的位操作技巧，这里不赘述。但是讲一些状压DP中最最基本的技巧: 我们要枚举 $m$ 列的所有 $01$ 状态，相当于枚举 $[0, 2^m)$ 中的所有数，所以循环就是从 $0$ 循环到 $1<<m-1$。

最后说一下其实我这个判断状态转移是否合法的办法并不高明，其实可以直接预处理出哪些状态是可以从某个状态转移而来的，但我太懒了就不想写了。。。还有一件事，这题的 $n,m$ 小的可怜，就算你写的复杂度巨大打表也是可以的 -_-

代码 Codes

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
62
63
64
65
66
67
68
69
70
71
72
73
74
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <cctype>
#include <cmath>
#define ll long long
using namespace std;
const int maxn=12;
int n,m,size;
bool is_ok[maxn][1<<11][1<<11];
ll f[1<<11][maxn]; //把大的放前面减小数组寻址的常数消耗

bool ok(int x,int y){
	int a[12],b[12];
	if(x&y)return 0;
	
	for(int i=1;i<=m;i++){//把数字拆分成二进制位
		a[i]=x&1;
		b[i]=y&1;
		x=x>>1; //二进制位向右移一位，也就是第一位消失了
		y=y>>1;
	}
	int num=0;
	for(int i=1;i<=m;i++){ 
    //上下两行都为0且连续的0的个数必须是偶数，因为只有00(两个0)能够转移到00
    //比如 010001  -> 100000 是不合法的
		if(a[i]||b[i]){
			if(num%2==1)return 0;
			num=0;
		}
		else num++;
	}
	if(num%2==1)return 0;
	
	return 1;
}

inline void pre(){ //预处理哪些情况是不合法的
	int fac[maxn];
	fac[0]=1;
	for(int i=1;i<=11;i++)fac[i]=fac[i-1]*2;
	for(int i=1;i<=11;i++){
		m=i;
		for(int j=0;j<fac[i];j++){
			for(int k=0;k<fac[i];k++){
				if(!ok(j,k))is_ok[i][j][k]=0;
				else is_ok[i][j][k]=1;
			}
		}
	}
	return ;
}
int main(){
	pre();
	
	while(scanf("%d %d",&n,&m)!=EOF&&(n||m)){
		size=1<<m; //相当于 2^m
		memset(f,0,sizeof(f));
		f[0][0]=1;
		
		for(int i=1;i<=n;i++){
			for(int j=0;j<size;j++){ //枚举第 i-1 行的状态
				for(int k=0;k<size;k++){ //枚举第 i 行的状态
					if(!is_ok[m][j][k])continue;
					f[j][i]+=f[k][i-1];
				}
			}
		}
		
		printf("%lld\n",f[0][n]); //为什么答案是这个自己去想
	}	
	return 0;
}