Description
在N×N的棋盘里面放K个国王，使他们互不攻击，共有多少种摆放方案。国王能攻击到它上下左右，以及左上左下右上右下八个方向上附近的各一个格子，共8个格子。
Input
只有一行，包含两个数N，K （ 1 <=N <=9, 0 <= K <= N * N）
Output
方案数。
Sample Input
3 2
Sample Output
16
首先这道题用到了名叫状压dp的算法
首先声明：这篇博客不适用于大神们!!!!!
看到互不侵犯的king这道题首先想到的是八皇后问题，但是发现和八皇后大不一样，因为八皇后是用的深搜的方法，但是由于根据国象的规则，一个棋盘能放的皇后要比国王少得多，所以DFS即可。
所以我们考虑其他的方法，因为国王的攻击范围很小，只有周围的一圈。但我们依然不能把所有的状态推出来（即使n<=9）。但我们可以发现只要确定了第一行，就可以将下面的用动规推出来。这样我们就可以用枚举的方式来做了。在枚举的同时，我们可以用二进制的方式来表示状态，这样较好比较，同时也可以压缩状态，这就是状压dp的思想。在这里可以模拟一下。
比如说n=5。 用1表示该格有国王，0反之。
1 1 1 1 1 这种情况显然是不存在的，我么就要把它排除掉。那么怎么排除呢？我们考虑用位运算的思想。将它 右移（>>）一位（因为国王的攻击范围只有1）。即 1 1 1 1 1再进行（&）运算，这样的返回值是1则出现冲突，再比如这种情况 1 0 1 0 1 1 1 1 1 1 。 1 0 1 0 1 这样的返回值是0，所以这种情况存在。而二进制我们可以直接用一个十进制数来表示。如 1 1 1 1 1 十进制是31，可以试一试计算 31&（31>>1）==1.而 1 0 1 0 1 十进制是21，
21&(21>>1)==0。比较时应该左移、右移都进行。另外我们还可以进行预处理。总状态数为 2^n-1，只进行循环即可，代码如下
int check2(int a)//一行自比 { if(a&(a<<1)) return 0; if(a&(a>>1)) return 0; return 1; } int get(int x)//计算状态为x，其中 1 的个数。 { int tot=0; while(x){ if(x&1) tot++; x=x>>1; } return tot; }int tot=(1<<n)-1; for(int i=0;i<=tot;i++) if(check2(i)){ zt[++num]=i;//状态 gs[num]=get(i);//该状态含的国王的个数 }
接下来讲dp的过程——
int f[10] (i) [600] (j) [82] (k) {0};//i为行数，j为第j种状态，k为当前总国王数 f[i][j][k]表示第i行状态为第j种放置了k个国王的方案数。
另外的一种预处理如下，对比两行的状态，可以加速dp过程中的比较。
int check1(int a,int b)//两行对比 { if(a&(b<<1)) return 0; if(a&(b>>1)) return 0; if(a&b)return 0;//对比两行时就需要对比不移动时的状态，至于为什么，自行脑补return 1; } for(int i=1;i<=num;i++)//pd[i][j]==1则表示i在上一行j在下一行，并且不冲突 for(int j=1;j<=num;j++) if(check1(zt[i],zt[j])) pd[i][j]=pd[j][i]=1;
主要的dp过程如下
for(int i=0;i<n;i++)//循环行数，对应f数组中的行数（i） for(int j=1;j<=num;j++)//循环状态，对应f数组中的（j） for(int k=0;k<=m;k++)//循环国王数，对应数组中的（k） if(f[i][j][k]) for(int q=1;q<=num;q++)//循环i下一行的状态 if(pd[j][q]&&(k+gs[q]<=m))//满足条件就继续 f[i+1][q][k+gs[q]]+=f[i][j][k]; long long int ans=0; for(int i=1;i<=num;i++)//把第n行的所有状态的f值相加即为答案 ans+=f[n][i][m];
这就是主要的函数，其他的自己加上的吧，光复制标程是没有意义的！！
注意：f[0][1][0]=1 即初始的状态。