题目描述
在N×N的棋盘里面放K个国王，使他们互不攻击，共有多少种摆放方案。国王能攻击到它上下左右，以及左上左下右上右下八个方向上附近的各一个格子，共8个格子。
输入输出格式
输入格式：
只有一行，包含两个数N，K （ 1 <=N <=9, 0 <= K <= N * N）
输出格式：
所得的方案数
输入输出样例
输入样例#1：
3 2
输出样例#1：
16
算法：
状压DP
分析：
这道题乍眼一看以为是搜索，其实不然，这道题实则是一道动规的题目。
虽然这道题目看上去和corn fields 求的东西不一样，CF那道题求的是方案数，这里求的是可行性的最大数，但是都是一堆的01串构成的（放与不放）。所以为了优化dp，这道题还是用状压dp。
同样的还是要初始化所有可行的状态和第一行的信息。这个很好理解，也不多说了。
但是这道题没这么简单，除了要记录上一维可行的状态之外，还要记录King的个数，将King也作为一个状态考虑。
上代码：
#include<cstdio>
#include<iostream>
#define C continue
using namespace std; int n,k;
long long dp[][][],king[],state[],tot,ans;
//dp[i][j][k]表示第i行选j状态在这一行及之前摆上k个国王的方案总数，state是状态，King是那一行的国王总数 inline void init() //初始化
{
int i;
tot=(<<n)-;
for (i=;i<=tot;i++)
if (!((i<<)&i)) //满足提议（同行）
{
state[++ans]=i;
int t=i;
while (t) //记录国王个数
king[ans]+=t%,t>>=; //注意是右移一位
}
} int main()
{
int i,j,p,s;
scanf("%d%d",&n,&k);
init();
for (i=;i<=ans;i++) //初始化第一行
if (king[i]<=k)
dp[][i][king[i]]=;
for (i=;i<=n;i++) //枚举行
for (j=;j<=ans;j++) //枚举这行方案
for (p=;p<=ans;p++) //枚举上行方案
{
if (state[j]&state[p])
C;
if (state[j]&(state[p]<<))
C;
if ((state[j]<<)&state[p])
C;
for (s=;s<=k;s++) //枚举国王个数
{
if (king[j]+s>k)
C;
dp[i][j][king[j]+s]+=dp[i-][p][s];
}
}
tot=;
for (i=;i<=n;i++)
for (j=;j<=ans;j++)
tot+=dp[i][j][k];
printf("%lld",tot);
return ;
}
状压dp的题主要要考虑如何优化状态，主要都是用01串来解决，其他的内容和普通dp基本是一样的。
嗯，就这样了。