题目描述
在N×N的棋盘里面放K个国王，使他们互不攻击，共有多少种摆放方案。国王能攻击到它上下左右，以及左上左下右上右下八个方向上附近的各一个格子，共8个格子。
注：数据有加强（2018/4/25）
输入输出格式
输入格式：
只有一行，包含两个数N，K （ 1 <=N <=9, 0 <= K <= N * N
输出格式：
所得的方案数
——————————————————————————
懵
#include<iostream>
#include<cstdio>
using namespace std;
int n,k;
long long dp[][][]; //dp[i][j][k]表示第i行，状态为j，前面摆了k个国王时，方案数；
long long state[] , king[] ;//state[]是当前状态，king[]是当前行的国王数；
long long ans , sum;//ans是用来记录状态总数的，sum是用来计算一共有多少种方案的；inline void inte()
{
int tot = (<<n) - ;//最多到这个时候，就是二进制下，每一位上都放上国王，当然有不行的，为了方便下文排除；
for(int i = ; i <= tot ; i++)
if(!((i<<)&i)) //因为要互不侵犯，所以，两个国王之间必须隔一个，这是判断是否满足题意国王之间不相互攻击；
{
state[++ans] = i; //找到了满足的，记录这个状态；
int t = i;
while(t) //判断这个状态有多少个国王，也就是t在二进制下有多少个1；
{
king[ans] += t%;
t>>=; //记住，是右移一位，和 t/=2 一样，就是稍微快一点；
}
}
}int main()
{
cin>>n>>k; //数据；
inte(); //初始化；
for(int i = ; i <= ans ; i++) //先处理第一行；
if(king[i] <= k) //一行的国王数一定不能超过总数；
dp[][i][king[i]] = ; for(int i = ; i <= n ; i++) //处理剩下的，所以从 2 开始枚举；
for(int j = ; j <= ans ; j++) //枚举状态；
for(int p = ; p <= ans ; p++) //再一遍状态，用来当作上一行的状态，因为 我们由上向下递推，能迎上本行的，只有上一行；
{
//这里就不在赘述了，和处理第一行同理，但是不同的是这里处理相邻的行，
if(state[j] & state[p]) continue; //所以，上下相邻不行
if(state[j] & (state[p]<<)) continue; //本行的右上角不能有国王；
if((state[j]<<) & state[p]) continue; //左上角也不行；
for(int s = ; s <= k ; s++)
{
//s表示本行以上用了多少国王； //满足条件后，还要记得国王数量是有限的！！
if(king[j] + s > k) continue; //我们是递推，所以本行以上一定处理完了，所以，本行加以前用过的国王，总数不能超过限定；
dp[i][j][king[j]+s] += dp[i-][p][s]; //还记得dp[i][j][k]中的k表示已经用过的国王数，而king[]是本行的，s是本行以前的；
}
} for(int i = ; i <= n ; i++) //因为不确定在哪一行用光国王，所以都枚举一遍；
for(int j = ; j <= ans ; j++)
sum += dp[i][j][k]; //本行及以前用光了国王，那么方案数加在总数中； cout<<sum;
return ;}
