Description
在N×N的棋盘里面放K个国王，使他们互不攻击，共有多少种摆放方案。国王能攻击到它上下左右，以及左上
左下右上右下八个方向上附近的各一个格子，共8个格子。
Input
只有一行，包含两个数N，K （ 1 <=N <=9, 0 <= K <= N * N）
Output
方案数。
Sample Input
3 2
Sample Output
16
正解：状压DP
解题报告：
一眼秒题，状压DP。棋盘放棋子的方案数，而且是小棋盘，果断状态压缩。
考虑用f[i][j][k]表示处理到第i行已经放了j个国王，第i行状态为k的方案数。
因为我们都是从上一行转移过来，所以首先预处理出某种状态能否存在（满足题意），状态与状态之间能否转移，并且计算每种状态是放了多少个国王。
一行行枚举，为了满足题意可以用位运算来快速检查是否满足题意。我这只蒟蒻一开始没想到用位运算。
每次枚举from状态和to状态，并且枚举上次放了多少个，直接转移即可。
1 //It is made by jump~ 2 #include <iostream> 3 #include <cstdlib> 4 #include <cstring> 5 #include <cstdio> 6 #include <cmath> 7 #include <algorithm> 8 #include <ctime> 9 #include <vector> 10 #include <queue> 11 #include <map> 12 #include <set> 13 #ifdef WIN32 14 #define OT "%I64d" 15 #else 16 #define OT "%lld" 17 #endif 18 using namespace std; 19 typedef long long LL; 20 int n,k,end; 21 LL ans; 22 LL f[10][100][700];//f[i][j][k]当前处理到第i行已经放了j个国王的状态为k的方案数 23 bool pd[700][700],ok[700]; 24 LL cnt[700]; 25 26 inline int getint() 27 { 28 int w=0,q=0; 29 char c=getchar(); 30 while((c<'0' || c>'9') && c!='-') c=getchar(); 31 if (c=='-') q=1, c=getchar(); 32 while (c>='0' && c<='9') w=w*10+c-'0', c=getchar(); 33 return q ? -w : w; 34 } 35 36 inline void Init(){ 37 end=(1<<n)-1; int x; 38 for(int i=0;i<=end;i++) { 39 if((i&(i>>1))!=0) continue; 40 ok[i]=true; 41 for(x=i;x;x>>=1) cnt[i]+=x%2; 42 f[1][cnt[i]][i]=1; 43 } 44 45 for(int i=0;i<=end;i++) { 46 if(ok[i]) 47 for(int j=0;j<=end;j++) { 48 if(ok[j]) { 49 if( (i&j)==0 && ((i>>1)&j)==0 && (i&(j>>1))==0 ) { //不在同一列，不在同一对角线 50 pd[i][j]=1; 51 } 52 } 53 } 54 } 55 } 56 57 inline void work(){ 58 n=getint(); k=getint(); 59 Init(); 60 for(int i=1;i<n;i++) //推下一个 61 for(int from=0;from<=end;from++) {//注意要有0，可以不放 62 if(!ok[from]) continue; 63 for(int to=0;to<=end;to++) { 64 if(!ok[to]) continue; 65 for(int j=cnt[from];j+cnt[to]<=k;j++){//枚举用了多少个 66 if(!pd[from][to]) continue; 67 f[i+1][j+cnt[to]][to]+=f[i][j][from]; 68 } 69 } 70 } 71 72 for(int i=0;i<=end;i++) ans+=f[n][k][i];//统计0，最后一行不放!!! 73 printf(OT,ans); 74 } 75 76 int main() 77 { 78 work(); 79 return 0; 80 }