poj 2411(状压DP)

poj 2411
设$dp(i, j)$为第$i$行用$j$(状态)的方案总数,注意这里$j$不是编号就是状态!
然后先把行可行的方案标记,然后按行DP要注意,横着的砖是11,竖着的砖是竖着的01,所以($h[i] $或$h[i-1]$)必须全是$1$,不然就会有空隙,然后最重要的是要注意($h[i]$与$h[i-1]$)一定是可行方案,否则会出现“半个砖横向填充”的情况。

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
#include<cstdio>
#include<cstring>
#include<algorithm>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define FN2 "poj2411"
using namespace std;
const int MAXN = 11 + 2;
int h, w, st[1<<MAXN];
LL dp[MAXN][1<<MAXN];//dp[i][j] 为第i行用j(状态)的方案总数
bool check(int x) {
int tot = 0;
while (x) {
if (x&1) tot++; else {
if ((tot&1)==1) return false;
tot = 0;
}
x>>=1;
}
if ((tot&1)==1) return false;
return true;
}
bool check2(int s1, int s2) {
return ((s1|s2)==(1<<w)-1) && (st[s1&s2]);
//s1|s2必须是满的,不然有空隙
//s1&s2必须是可行方案,否则会有横着摆的砖是奇数
}
void clean() {
ms(st, false), ms(dp, 0);
}
void solve() {
clean();
if (w>h) swap(h, w);
for (int i=0;i<(1<<w);i++) if (check(i)) st[i] = true;
for (int i=0;i<(1<<w);i++) {
if (st[i]) dp[1][i] = 1;
}
for (int hi=2;hi<=h;hi++) {
for (int i=0;i<(1<<w);i++) {
for (int j=0;j<(1<<w);j++) {
if (dp[hi-1][j]==0) continue;
if (check2(i, j)) {
dp[hi][i] += dp[hi-1][j];
}
}
}
}
printf("%lld\n", dp[h][(1<<w)-1]);
}
int main() {
#ifndef ONLINE_JUDGE
freopen(FN2".in", "r", stdin); freopen(FN2".out", "w", stdout);
#endif
while (scanf("%d%d", &h, &w)==2&&h&&w) solve();
fclose(stdin); fclose(stdout);
return 0;
}
------ 本文结束 ------