2010年1月11日星期一.sgu131 pku2411
状态压缩动态规划。
pku2411:
给一个m*n(m,n<=11)的棋盘，用1*2和2*1的矩形覆盖这个棋盘，问有多少中方法对这个棋盘进行
完全覆盖。
这题有组合数学上的公式，但是只能对棋盘上没有障碍的情况有用，如果遇到有障碍的情况，只能
利用容斥原理进行计算，但是进行容斥原理的会非常复杂。
其实一看到数据范围就应该想到使用位运算的状态压缩动态规划。
主要的程序是
a表示要铺满的这一行的状态,b表示的是铺满上一行的状态a产生的下一行状态。
然后使用状态b继续递推。
1
2 #include<iostream>
3 #include<cstdio>
4 #include<cstdlib>
5 #include<cstring>
6 #include<algorithm>
7 using namespace std;
8 typedef long long LL;
9 const int maxint = 0x7fffffff;
10 const long long max64 = 0x7fffffffffffffffll;
11 #define bin(i) (1 << i) /*1左移i位*/
12 #define emp(a,i) (!(a & bin(i))) /*判断a的i位是否位0*/
13
14 const int N = 1 << 11;
15 LL f[N], g[N];
16 int m, n;
17 int full;
18
19 void dfs(int a, int b, LL k)
20 {
21 if (a == full) { //将a铺满之后形成的所有下一行状态b的铺法都有k种
22 g[b] += k; //产生b的所有状态求和
23 return;
24 }
25 for (int i = 0; i < m; i++) {
26 if (emp(a, i)) {
27 if (i < m - 1 && emp(a, i + 1)) {
28 dfs(a | bin(i) | bin(i + 1), b, k); //横铺
29 }
30 if (emp(b, i)) {
31 dfs(a | bin(i), b | bin(i), k); //竖铺
32 }
33 break;
34 }
35 }
36 }
37
38 int main()
39 {
40 int i, j, k;
41 while(scanf("%d%d", &m, &n) == 2 && m && n) {
42 memset(f,0,sizeof(f));
43 memset(g,0,sizeof(g));
44 full = (1 << m) - 1;
45 f[full] = 1;
46 for (k = 0; k <= n; k++) {
47 for (i = 0; i <= full; i++) {
48 if (f[i]) { //如果此行的状态i可达
49 dfs(i, 0, f[i]);
50 }
51 }
52 for (i = 0; i <= full; i++) {
53 f[i] = g[i];
54 g[i] = 0;
55 }
56 }
57 cout << f[0] << endl;
58 }
59 return 0;
60 }
61
sgu131:pku2411的加强版
多了L型的瓷砖。这个最好是自己考虑一下，其实就是比上边的代码多了几行
const int N = 512;
LL f[N], g[N];
int m, n;
int full;
void dfs(int a, int b, LL k)
{
if (a == full) { //将a铺满之后形成的所有下一行状态b的铺法都有k种
g[b] += k;
return;
}
for (int i = 0; i < m; i++) {
/* 六种铺法，按以下顺序分别是
a:## ## ## # # #
b: # # # ## ##
* */
if (emp(a, i)) {
if (i < m - 1 && emp(a, i + 1)) {
dfs(a | bin(i) | bin(i + 1), b, k);
if (emp(b, i))
dfs(a | bin(i) | bin(i + 1), b | bin(i), k);
if (emp(b, i + 1))
dfs(a | bin(i) | bin(i + 1), b | bin(i + 1), k);
}
if (emp(b, i)) {
dfs(a | bin(i), b | bin(i), k);
if (i > 0 && emp(b, i - 1))
dfs(a | bin(i), b | bin(i) | bin(i - 1), k);
if (i < m - 1 && emp(b, i + 1))
dfs(a | bin(i), b | bin(i) | bin(i + 1), k);
}
break;
}
}
}