题目描述

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

注:数据有加强(2018/4/25)

输入输出格式

输入格式:

只有一行,包含两个数N,K ( 1 <=N <=9, 0 <= K <= N * N)

输出格式:

所得的方案数

输入输出样例

输入样例#1: 

3 2
输出样例#1: 

16

思路:

这题一看n<=9,二话不说就上状压DP。

f[i][j][k]表示第i行,状态为j,共k个国王时的方案数。

为了减小常数,我们可以先预处理出所有满足要求的状态,存在s数组里,再用sum数组存储当前状态有几个国王。

判断上下是否符合要求也十分简单,乱&一下就可以了,在我的代码中,f[i][j][k]中的j表示第j个状态。

代码:

 #include"bits/stdc++.h"
#define db double
#define ll long long
#define vec vector<ll>
#define Mt vector<vec>
#define ci(x) scanf("%d",&x)
#define cd(x) scanf("%lf",&x)
#define cl(x) scanf("%lld",&x)
#define pi(x) printf("%d\n",x)
#define pd(x) printf("%f\n",x)
#define pl(x) printf("%lld\n",x)
//#define rep(i, x, y) for(int i=x;i<=y;i++)
#define rep(i,n) for(int i=0;i<n;i++)
const int N = 1e5+;
const int mod = 1e9 + ;
const int MOD = mod - ;
const int inf = 0x3f3f3f3f;
const db PI = acos(-1.0);
const db eps = 1e-;
using namespace std;
int n,m;
int sum[N];
int s[N];
ll f[][][];
int id=;
int cal(int x){
int ans=;
while(x) ans+=x&,x>>=;
return sum[id]=ans;
}
int main(){
ci(n),ci(m);
int x=(<<n);
for(int i=;i<x;i++) if(!(i&(i<<))) f[][++id][cal(i)]=,s[id]=i;//预处理一行内不冲突的情况
for(int i=;i<=n;i++){
for(int j=;j<=id;j++){
for(int k=;k<=id;k++){
if((s[j]&s[k])||(s[j]&(s[k]>>))||(s[j]&(s[k]<<))) continue;//前后两行不冲突
for(int l=;l+sum[j]<=m;l++) f[i][j][l+sum[j]]+=f[i-][k][l];
}
}
}
ll ans=;
for(int i=;i<=id;i++) ans+=f[n][i][m];//累加
pl(ans);
return ;
}
05-11 21:46