[SCOI2005]互不侵犯King

Time Limit:10000MS  Memory Limit:165536K
Total Submit:13 Accepted:9
Case Time Limit:1000MS

Description

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

Input

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

Output

方案数。

Sample Input

3 2

Sample Output

16

Source

今天早上我一直在被题虐。。看了7、8道没一道会的，我真是太菜了55555
好不容易看到道会的还这么水。。囧死了。。
61.187.179.132:8080/JudgeOnline/showproblem
额。这道题目首先dfs出所有可能的状态（不能有连续的1）。。然后预处理出所有数中1的个数。然后直接DP就OK了。。
Code：
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<cstring>
#define rep(i,n) for(int i=0;i<n;i++)
#define pb push_back
using namespace std;
const int inf=~0U>>1,maxn=9,maxk=maxn*maxn;
typedef long long ll;
ll dp[2][maxk+1][1<<maxn]={0};
int state[1<<maxn],cnt=0,N,K,C[1<<maxn];
void dfs(int p,int s)
{
if(p==N){state[cnt++]=s;return;}
dfs(p+1,s*2);
if(!(s&1))dfs(p+1,s*2+1);
}
inline bool Legal(int a,int b)
{
a=state[a];b=state[b];
return !(a&b)&&!((a<<1)&b)&&!((a>>1)&b);
}
inline int Count(int a)
{
a=state[a];
return C[a];
}
int main()
{
//freopen("in","r",stdin);
cin>>N>>K;
int now=0,old=1;
dp[now][0][0]=1;dfs(0,0);
C[0]=0;
for(int i=1;i<(1<<N);i++)
C[i]=C[i/2]+(i&1);
rep(n,N)
{
swap(now,old);memset(dp[now],0,sizeof(dp[now]));
rep(k,K+1)rep(ps,cnt)rep(ns,cnt)
if(k-Count(ns)>=0&&Legal(ns,ps))
{
dp[now][k][ns]+=dp[old][k-Count(ns)];
}
}
ll ans=0;
rep(s,cnt) ans+=dp[now][K][s];
cout<<ans<<endl;
}