洛谷P1896 [SCOI2005] 互不侵犯 题解

题目链接：P1896 [SCOI2005] 互不侵犯

题意：

在 $n \times n$ 的棋盘里面放 $K$ 个国王，并使他们互不攻击，求合法摆放方案数。

国王能攻击到它上下左右，以及左上左下右上右下八个方向上附近的各一个格子，共 $8$ 个格子。

输入格式：

一行，包含两个数 $n,k~(1 \le n \le 9, 0 \le K \le n^2)$

输出格式：

所得的方案数。

退役后的第一篇题解，作为复习（？

简单的状压dp。设 $f_{i,j,k}$ 表示第 $i$ 行的状态为 $j$ （ $j$ 必须自身合法 ），且已经用了 $k$ 个国王的方案数

$$\large f_{i,j,k} =\sum f_{i-1,l,k-\mathrm{popc}(j)}$$

其中 $l$ 为上一行的状态，且 $l,j$ 没有“相接”的地方，$\mathrm{popc}(j)$ 表示这一行放了 $j$ 个国王。

答案就是 $\sum f_{n,i,K}$ ，其中 $i$ 为所有合法的状态。

时间复杂度 $\mathcal{O}(nK4^n)$

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define popc(a) __builtin_popcountll(a)
#define N ((int)())

int n,K,cnt,popc[1 << 9],f[11][1 << 9][105];
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n >> K; int mx = (1ll << n) - 1, res = 0;
    for(int i=0; i<=mx; i++) f[1][i][popc(i)] = 1;
    for(int i=2; i<=n; i++)
        for(int j=0; j<=mx; j++) if(!(j & (j << 1)))
            for(int k=popc(j); k<=K; k++)
                for(int l=0; l<=mx; l++) if(!(l & (l << 1)) && (!(j & l)))
                {
                    if((!(l & (j << 1))) && (!(l & (j >> 1))))
                        f[i][j][k] += f[i - 1][l][k - popc(j)];
                }
    for(int i=0; i<=mx; i++) if(!(i & (i << 1))) res += f[n][i][K];
    cout << res << '\n';
    return 0;
}