一、题目
Description
在N×N的棋盘里面放K个国王，使他们互不攻击，共有多少种摆放方案。国王能攻击到它上、下、左、右，以及左上、左下、右上、右下八个方向上附近的各一个格子，共8个格子。
Input
只有一行，包含两个数N，K （ 1 <=N <=9, 0 <= K <= N * N）
Output
方案数
Sample Input
3 2
Sample Output
16
原题链接→_→bzoj1087: [SCOI2005]互不侵犯King
二、题目分析
其实我们可以用一张美妙的表来解决这道题（划掉）这道题我们首先考虑暴搜解决，然而似乎状态略多会炸……
搜索不行，我们很容易能想到DP，这里我们引入一个神奇的DP——状态压缩型动态规划。状态压缩是状压DP的核心（废话！），本人在上一篇blog中详细介绍了状态压缩的思想，诸位看官不妨移步一看，可能会对理解状压DP起到一定帮助（链接→_→【宽度优先搜索】神奇的状态压缩 CodeVs1004四子连棋）
对于每一行的状态，我们用1表示国王，0表示不放国王。由于每个位置只有0和1两种状态，我们可以使用位运算判断每行的状态是否合法。例如：10101010就是一种合法状态，而11111111就不合法。每行状态表示的十进制数就是我们压缩后的状态。
我们需要做两个预处理，先枚举每行所有可能的状态，记录下合法状态。然后判断两个状态是否能作为临行放置，并用布尔类型的二维数组存储其关系。
预处理之后，就是常规的DP，状态转移方程如下：
f[i][j][now]=∑f[i-1][j-num[now]][q]
略作说明：f[i][j][k]代表前i行，总共放j个国王，第i行状态为k时的方案数。状态转移方程中的num[now]代表状态为now的行中国王的数目，q表示第i-1行的状态。
三、代码实现
#include<stdio.h>
int n,k;
long long ans;
bool s[],map[][];//判断状态是否合法；判断两个状态是否能作为临行
int num[];//num[i]代表编号为i的状态含有的国王数
long long f[][][];
int sum;
void pre_s()//预处理s数组
{
int i;
for(i=;i<sum;++i)
{
if((i&(i<<))==)
{
s[i]=true;
int t=i,cnt=;
while(t)
{
cnt+=(t&);
t>>=;
}
num[i]=cnt;
f[][cnt][i]=;
}
}
}
void pre_map()//预处理map数组
{
int i,j;
for(i=;i<sum;++i)
{
if(!s[i])continue;
for(j=;j<sum;++j)
{
if(!s[j])continue;
if((!(i&j))&&(!((i<<)&j))&&(!((i>>)&j)))map[i][j]=true;
}
}
}
void dp()
{
int i,j,now;
for(i=;i<=n;++i)
for(j=;j<=k;++j)
for(now=;now<sum;++now)
{
if(!s[now])continue;
if(num[now]>j)continue;
int q;
for(q=;q<sum;q++)
{
if(!s[q])continue;
if(!map[now][q])continue;
if(num[q]+num[now]>j)continue;
f[i][j][now]+=f[i-][j-num[now]][q];
}
}
}
int main()
{
scanf("%d%d",&n,&k);
sum=<<n;
pre_s();
pre_map();
dp();
for(int i=;i<sum;++i)
{
if(!s[i])continue;
ans+=f[n][k][i];
}
printf("%lld",ans);
return ;
}
bzoj1087 互不侵犯king
弱弱地说一句，本蒟蒻码字也不容易，转载请注明出处http://www.cnblogs.com/Maki-Nishikino/p/5992703.html