BZOJ1087【SCOI2005】互不侵犯King <状压DP>

Problem

【SCOI2005】互不侵犯King

$\mathrm{Time\;Limit:\;10\;Sec}$
$\mathrm{Memory\;Limit:\;162\;MB}$

Description

在$N\times N$的棋盘里面放$K$个国王，使他们互不攻击，共有多少种摆放方案。国王能攻击到它上下左右，以及左上左下右上右下八个方向上附近的各一个格子，共$8$个格子。

Input

只有一行，包含两个数$N$, $K$ ($1 \le N \le 9$, $0 \le K \le N^2$)

Output

方案数。

Sample Input

3 2

Sample Output

16

标签：状压DP

Solution

状压$DP$的基础题。
对于每个国王，不难发现它放与不放只与当行和前一行有关，而它放完后的影响只作用于当行和后一行。
而$N\le 9$
于是考虑状压$DP$，$f[i][j][k]$表示当前考虑到第$i$行，共用了$j$个国王，第$i$行状态为$k$的方案数。那么$k$和前一行的状态$k'$是否冲突可以用$k$、$k<<1$、$k>>1$与$k'$取$\&$得到。时间复杂度$O(n^2\times 2^k\times 2^k)$。

Code

#include <iostream>
#include <cstdio>
using namespace std;
typedef long long lnt;
int n, k, cnt[100], sta[1000], tot;
lnt f[10][1000][1000], ans;    bool mrk[1000];
void init() {
    for (int i = 0; i < (1<<n); i++) {
        if (i&(i<<1))	continue;
        mrk[i] = true, sta[tot++] = i;
        for (int j = i; j; j >>= 1)	cnt[i] += (j&1);
        f[1][cnt[i]][i] = 1;
    }
}
int main() {
    scanf("%d%d", &n, &k), init();
    for (int i = 2; i <= n; i++)	for (int j = 0; j <= k; j++)	for (int p = 0; p < tot; p++) {
        int cur = sta[p];	if (cnt[cur] > j)	continue;
        for (int q = 0; q < tot; q++) {
            int lst = sta[q];
            if ((cur&lst) || ((cur<<1)&lst) || ((cur>>1)&lst))	continue;
            f[i][j][cur] += f[i-1][j-cnt[cur]][lst];
        }
    }
    for (int i = 0; i < tot; i++)	ans += f[n][k][sta[i]];
    printf("%lld", ans);
    return 0;
}