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