Bzoj 1087(状压DP)

Bzoj 1087
设$dp(i,j,st(S))$为前$i$行安放了$j$个国王,$i$行使用$st(S)$状态的方案数。
$$dp(i,j,st(S))=\sum dp(i-1.j-num_s, st(k))$$
其中$st(S)$与$st(k)$不冲突。
初值:$dp(1, num(S), st(S)) = 1$,其中$S$是合法状态,其他值设为$0$。
然后求解即可,注意答案只在最后一行,累加不要加错了,然后dp数组也要开longlong,否则WA

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
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
using namespace std;
const int MAXN = 9 + 2, MAXK = 100 + 5;
int n, m, st[1 << MAXN], num[1 << MAXN], tot;
LL dp[MAXN][MAXK][1 << MAXN];
int count(int S) {
int ret = 0, t = S;
while (t) ret++, t &= (t - 1);
return ret;
}
bool check(int S) {
if (S & (S >> 1)) return false;
return true;
}
bool check2(int a, int b) {
int ta = a, x = 1;
while (ta) {
if (ta & 1 == 1) {
if (x < n && ((b >> (x)) & 1) == 1) return false;
if (x - 1 >= 0 && ((b >> (x - 1)) & 1) == 1) return false;
if (x - 2 >= 0 && ((b >> (x - 2)) & 1) == 1) return false;
}
ta >>= 1, x++;
}
return true;
}
void clean() {
ms(num, 0), ms(st, 0), ms(dp, 0), tot = 0;
}
void solve() {
clean();
for (int S=0;S<(1<<n);S++) if (check(S)) st[++tot] = S, num[tot] = count(S);
for (int i=1;i<=tot;i++) dp[1][num[i]][i] = 1;
for (int i=2;i<=n;i++) {
for (int j=0;j<=m;j++) {
for (int k=1;k<=tot;k++) {
for (int l=1;l<=tot;l++) {
if (!check2(st[l], st[k])) continue;
dp[i][j][k] += dp[i - 1][j - num[k]][l];
}
}
}
}
LL ans = 0;
for (int j=1;j<=tot;j++) {
ans += dp[n][m][j];
}
printf("%lld\n", ans);
}
int main() {
#ifndef ONLINE_JUDGE
freopen("1.in", "r", stdin);freopen("1.out", "w", stdout);
#endif
scanf("%d%d", &n, &m), solve();
return 0;
}

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