poj 3254(状压DP)

poj 3254
状态压缩基础题。
题意是有一个矩阵,数为0的地方可以放牛,且牛不可以上下左右相邻,求摆放方案数。
DP解答,我们每行DP,但是这里状态比较复杂,这里要用到状压DP
设$dp(i, st[j])$为第$i$行使用状态$j$的方案数。
状态转移方程:
$$dp(i, st[j]) = \sum dp(i-1, st[k])$$
其中$k$是满足$k$在$i-1$行时与$j$在$i$行时不相邻的状态。
代码中运用了多处位运算技巧。

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
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
using namespace std;
const int MAXN = 12 + 2;
int m, n;
int cur[MAXN], st[1<<MAXN], top, dp[MAXN][1<<MAXN];//输入状态,可行状态,可行状态个数,dp[i][st[j]]为第i行使用状态j的总方案.其中cur中1为不可放置, st中1为放置点
bool fit(int j, int h) {return (st[j]&cur[h]) ? false : true;}
void clean() {
top = 0, ms(cur, 0), ms(dp, 0);
}
void solve() {
clean();
for (int i=0;i<(1<<n);i++) {//处理可行状态(无相邻)
if (i&(i>>1)) continue; else st[++top] = i;
}
for (int i=1;i<=m;i++) for (int j=1;j<=n;j++) {//处理输入
int x; scanf("%d", &x);
if (!x) cur[i] += (1<<(j-1));
}
for (int i=1;i<=top;i++) if (fit(i, 1)) dp[1][i] = 1;//初始化DP
for (int hi=2;hi<=m;hi++) {//DP
for (int j=1;j<=top;j++) {
if (!fit(j, hi)) continue;
for (int k=1;k<=top;k++) {
if (!fit(k, hi-1)) continue;
if (st[j]&st[k]) continue;
dp[hi][j] = (dp[hi][j] + dp[hi-1][k])%100000000;
}
}
}
int ans = 0;
for (int i=1;i<=top;i++) ans = (ans+dp[m][i])%100000000;
printf("%d\n", ans);
}
int main() {
#ifndef ONLINE_JUDGE
freopen("1.in", "r", stdin);freopen("1.out", "w", stdout);
#endif
while (scanf("%d%d", &m, &n)==2) solve();
return 0;
}

------ 本文结束 ------