【洛谷P1896】互不侵犯【状压dp】

本文主要是介绍【洛谷P1896】互不侵犯【状压dp】，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目大意：

题目链接：https://www.luogu.org/problemnew/show/P1896
在 $N\times N$ 的棋盘里面放 $K$ 个国王，使他们互不攻击，共有多少种摆放方案。国王能攻击到它上下左右，以及左上、左下、右上、右下八个方向上附近的各一个格子，共8个格子。

思路：

由于棋盘最大只有 $9\times 9$ ，所以可以考虑使用状压 $d p$ 。
设 $f [i] [j] [k]$ 表示第 $i$ 行，状态为 $j$ ，前 $i$ 行已经放了 $k$ 个国王的方案数。
显然还需要枚举上一行的状态。为了满足任意两个国王不能斜线、直线上相邻，所以需要判断上一行的状态和这一行的状态是否满足

x&y=0
x&(y<<1)=0
x&(y>>1)=0

其中 $x, y$ 分别表示这一行的状态和上一行的状态。
可以先把所有合法的状态（即这一行内没有任何两个国王相邻）预处理出来，顺便初始化 $f$ 数组和 $s$ 数组， $s$ 数组表示这个状态中放置了几个国王。
然后就不用枚举状态，直接枚举合法状态集合的编号。
设 $i$ 表示第 $i$ 行， $j$ 表示这一行的状态是第 $j$ 个合法状态， $k$ 表示上一行的状态是第 $k$ 个合法状态，前 $i - 1$ 行放了 $l$ 个王的方案数。
转移方程就是
$f [i] [j] [l + s [j]] + = f [i - 1] [k] [l]$
答案就是 $\sum^{cnt}_{i=0}f[n][i][m]$
其中 $c n t$ 表示有多少个合法状态。
需要开 $long\ long$ 。时间复杂度 $O(nm\times cnt^2)$ 。

代码：

#include <cstdio>
using namespace std;
typedef long long ll;const int MAXN=(1<<9);
int n,m,maxn,cnt,q[MAXN],s[MAXN];
ll f[10][MAXN][100],ans;bool check(int x)  //判断这个状态是否是合法状态
{ bool flag=0;while (x){if (x&1&&flag) return 0;if (x&1) flag=1;else flag=0;x>>=1;}return 1;
}int count(int x)  //这个状态中放置了多少个国王
{int sum=0;while (x){sum+=(x&1);x>>=1;}return sum;
}bool check_push(int x,int y)  //判断这两行是合法
{if (x&y) return 0;if (x&(y<<1)) return 0;if (x&(y>>1)) return 0;return 1;
}int main()
{scanf("%d%d",&n,&m);maxn=(1<<n);for (int i=0;i<maxn;i++)if (check(i)){q[++cnt]=i;s[cnt]=count(i);f[1][cnt][s[cnt]]=1;}for (int i=2;i<=n;i++)for (int j=1;j<=cnt;j++)for (int k=1;k<=cnt;k++)if (check_push(q[j],q[k]))for (int l=0;l<=m-s[j];l++)f[i][j][l+s[j]]+=f[i-1][k][l];for (int i=1;i<=cnt;i++)ans+=f[n][i][m];printf("%lld",ans);return 0;
}