洛谷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;
}