洛谷 1896 [SCOI 2005] 互不侵犯 (状压DP)

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

https://www.luogu.org/problemnew/show/P1896
题意：求在N×N的棋盘里面放K个国王，使他们互不攻击，共有多少种摆放方案。国王能攻击到它上下左右，以及左上左下右上右下八个方向上附近的各一个格子，共8个格子。其中 $1 <=N <=9,\ 0 <= K <= N * N$ 。

类似于炮兵阵地(NOI2001)的状压DP，不同之处就是那个题是要求最多能摆放的炮兵部队的数量，这个要求的是方案数，但原理类似。
令 $dp[i][j][k]$ 表示在第 $i$ 行状态为 $j$ ，前 $i$ 行共放了 $k$ 个国王的方案数。其中 $j$ 的二进制表示这一行的摆放方案，这一位为 $1$ 表示放国王， $0$ 表示不放。显然当前行只受上一行限制且只限制下一行，那么我们用 $now$ 表示当前行的状态， $pre$ 表示上一行的状态， $tmp$ 表示这一行 $now$ 这个状态有多少国王，就可以得到转移方程如下：

d p [i] [n o w] [j] = \sum d p [i - 1] [p r e] [j - t m p]

$dp[i][now][j]=\sum dp[i-1][pre][j-tmp]$
当然这里的

now n o w $now$ 和

pre p r e $pre$ 是要合法的，所以枚举

now n o w $now$ 和

pre p r e $pre$ ，判断合法并顺便计算出状态

now n o w $now$ 有多少个国王(即

now n o w $now$ 的二进制有多少个1)，再进行转移。最后答案

ans=∑dp[n][j][k] a n s = ∑ d p [ n ] [ j ] [ k ] $ans=\sum dp[n][j][k]$ 。
要注意的是结果可能爆int，要记得开long long。

#include<iostream>
#include<cstdio>
#include<stack>
#include<algorithm>
#include<cstring>
#include<map>
#include<queue>
#include<cmath>using namespace std;int n,k;
long long ans;
long long dp[12][1030][85];int check(int p,int q)
{int a[20],b[20];memset(a,0,sizeof(a));memset(b,0,sizeof(b));int i=1,cnt=0;while(p){a[i]=p%2;p/=2;i++;}i=1;while(q){b[i]=q%2;q/=2;i++;}for(i=1;i<=n;i++){if(a[i]==1){if(b[i]==1||b[i-1]==1||b[i+1]==1) return -1;if(a[i-1]==1||a[i+1]==1) return -1;}if(b[i]==1){if(a[i]==1||a[i-1]==1||a[i+1]==1) return -1;if(b[i-1]==1||b[i+1]==1) return -1;cnt++;}}return cnt;
}int main()
{scanf("%d%d",&n,&k);for(int i=0;i<=(1<<n)-1;i++){int tmp=check(0,i);if(tmp!=-1)dp[1][i][tmp]=1;}for(int i=2;i<=n;i++){for(int pre=0;pre<=(1<<n)-1;pre++){for(int now=0;now<=(1<<n)-1;now++){int tmp=check(pre,now);if(tmp!=-1){for(int j=k;j>=tmp;j--)dp[i][now][j]+=dp[i-1][pre][j-tmp];}}}}for(int j=0;j<=(1<<n)-1;j++)ans+=dp[n][j][k];printf("%lld",ans);return 0;
}