题目：在N*N的棋盘里面放k个国王，使他们互不攻击，共有多少种摆放方案。国王能攻击到它上下左右，以及左上左下右上右下八个方向上附近的各一个格子，共8个格子。
输入输出：输入N,K，输出有几种放置方法。（N<=9,k<=n^2）
样例输入输出：
入:3 2
出：16
这道题看范围就显然是状压dp了吧。。。
其实这道题和状压基础题玉米地（corn fields）非常相像，主要思路包括以下几点。
1.同一行不能有相邻的国王。
2.斜对角和正上正下不能有相邻的国王。
3.一共只有k个国王。
根据状压dp的一般尿性，肯定是要枚举状态的，那状态里面“ 1 ”，“ 0 ”表示什么含义呢？
肯定是“ 1 ”表示这一行这个位置放国王，“ 0 ”表示不放啊（废话++）
那思路就挺显然了。
1.枚举状态S,判断（S&(S<<1)）==0,只有这样的S才是合法状态
2.枚举上一行状态s，判断（(S&（s<<1）)==0&&(S&(s>>1))==0&&(S&s)==0）分别对应右上，左上，正上。
3.主要麻烦的是这个k，怎么处理已经放了多少国王呢，这里我们可以用类似背包的思想，新开一维表示已经放入的国王数，然后由上一行较少国王数的状态转移过来（是不是很像背包的二维代码那个转移？可以把国王总数看作背包的容量，每一个国王就是背包中的一个个物品）
然后就没了。。。
附上全部代码：
#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> using namespace std; const int maxn=1e2+10; typedef long long LL; LL f[15][1<<10][80]; int lowbit(int x){return x&-x;} int find(int x){ int cnt=0; for(int i=x;i;i-=lowbit(i)){ cnt++; } return cnt; } int main(){ int n,k; scanf("%d%d",&n,&k); int Max=(1<<n)-1; f[0][0][0]=1; for(int i=1;i<=n;i++){ for(int S=0;S<=Max;S++){ int cnt=find(S); if((S&(S>>1))==0){ for(int s=0;s<=Max;s++){ if((S&s)==0 && ((S&(s<<1))==0) && (S&(s>>1))==0) for(int kk=cnt;kk<=k;kk++){
//这里用kk保存这一行所放置的国王数，要注意，在S状态下，已经有cnt个国王放置了，所以要从这再往上遍历 f[i][S][kk]+=f[i-1][s][kk-cnt]; } } } } } LL ans=0; for(int S=0;S<=Max;S++){ ans+=f[n][S][k]; } printf("%lld",ans); return 0; }