[bzoj1087][DP][状态压缩]互不侵犯King

本文主要是介绍[bzoj1087][DP][状态压缩]互不侵犯King，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Description

在N×N的棋盘里面放K个国王，使他们互不攻击，共有多少种摆放方案。国王能攻击到它上下左右，以及左上左下右上右下八个方向上附近的各一个格子，共8个格子。

Input

只有一行，包含两个数N，K （ 1 <=N <=9, 0 <= K <= N * N）

Output

方案数。

Sample Input

3 2

Sample Output

16

HINT

N，K （ 1 <=N <=9, 0 <= K <= N * N）

题解

嗯。最近学的状态压缩，一道不错的状态压缩题。我们开一个三维的dp数组。dp[i][j][k]表示第i行，第j个状态（二进制的j。0表示不放国王，1表示放国王），到目前共使用了k个国王（包括本行）的最多方案数。状态转移方程就是dp[i][j][k]=dp[i][j][k]+dp[i-1][l][k-sum[i]] (l表示上一行与j可以匹配的方案，sum[i]表示第i个状态的人数).
这样我们就可以开心地用状态压缩做啦~第一道自己ac的bzoj题，很开心~

代码
update 2017/10/28
原先的代码太丑了。。不符合风范，改一改

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
using namespace std;
typedef long long LL;
LL f[10][1100][90];//i行 排列为j 共放k个 
int bin[11],n,kk;
int tmp[1100],tp,pos[1100];
int main()
{bin[1]=1;scanf("%d%d",&n,&kk);for(int i=2;i<=n+1;i++)bin[i]=bin[i-1]*2;memset(f,0,sizeof(f));tp=0;for(int i=0;i<=(1<<n)-1;i++)if((i&(i<<1))==0){int s=0;for(int j=1;j<=n;j++)if((i&bin[j])!=0)s++;f[1][i][s]++;tmp[++tp]=i;pos[tp]=s;}for(int i=2;i<=n;i++)for(int j=1;j<=tp;j++)for(int k=1;k<=tp;k++){if((tmp[j]&tmp[k])==0 && (tmp[j]&(tmp[k]<<1))==0 && (tmp[j]&(tmp[k]>>1))==0){for(int l=pos[k];l<=kk-pos[j];l++)f[i][tmp[j]][l+pos[j]]+=f[i-1][tmp[k]][l];}}LL ans=0;for(int i=1;i<=tp;i++)ans+=f[n][tmp[i]][kk];printf("%lld\n",ans);return 0;
}