Luogu P1896 [SCOI2005]互不侵犯 题解

Describe

题目链接

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

注：数据有加强（2018/4/25）

1 <=N <=9, 0 <= K <= N * N

Solution

状压DP。

判断两个国王是否相互干扰：$i\&j(i<<1)\&ji\&(j<<1)$。

设$f[i][j][k]$表示第$i$行状态$j$，布置了$k$个国王的方案数。

$$f[i][j][k]+=f[i][p][k-sum[j]]$$

Code

#include<bits/stdc++.h>
#define int long long //10年OI一场空，不开long long见祖宗
using namespace std;
int n,K,f[11][1<<10][100],S[1<<10],sum[1<<10],cnt,ans;
signed main(){
cin>>n>>K;
for(int i=0;i<(1<<n);i++){
if(i&(i<<1)) continue ;
S[++cnt]=i;
for(int j=0;j<n;j++)
if((1<<j)&i) sum[cnt]++;
}
f[0][1][0]=1;//初始化
for(int i=1;i<=n;i++){
for(int j=1;j<=cnt;j++){
for(int k=0;k<=K;k++){
if(k<sum[j]) continue ;
for(int p=1;p<=cnt;p++){
if(S[p]&S[j]S[p]&(S[j]<<1)(S[p]<<1)&S[j]) continue ;//是否干扰
f[i][j][k]+=f[i-1][p][k-sum[j]];//DP
}
}
}
}
for(int i=1;i<=cnt;i++) ans+=f[n][i][K];//最终答案求和
cout<<ans<<endl;
}