洛谷1377 M国王 （SCOI2005互不侵犯King）
本题地址：http://www.luogu.org/problem/show?pid=1377
题目描述
天天都是n皇后，多么无聊啊。我们来一道m国王游戏吧！
题目是这样的，在n*n的格子里放m个国王，使他们不互相攻击，有多少种放法呢？（可以为0）
国王的攻击力大不如皇后，他只能对与他相邻的8个格子产生攻击。
输入输出格式
输入格式：
n,m
输出格式：
方案数
输入输出样例
输入样例#1：
1 1
输出样例#1：
1
说明
数据范围：
100%的数据满足n<=8,m<=n*n
时限2秒（保证正常代码可以在时限内通过）
【思路】
状态压缩DP。
注意这个题与n皇后的差别：可以有多个国王放在同一行。
设d[i][s1][j]表示放到第i行 第i行放置状态为s1 且已经放了j个 的方案数。s用二进制表示。则有转移方程如下：
d[i][s1][j]
+= d[i-1][s2][j-cnt[s1]]
其中cnt表示状态中放置的国王数。
优化：注意到不是每一个状态都是有用的，也不是任两个状态可以互相转移。因此可以提前筛去自身不符合要求的状态(can)，同时建立状态之间的边(has_edge)。
【代码】
#include<iostream>
#include<cstring>
using namespace std; const int maxn = <<; typedef long long LL;
LL d[][maxn][*];
int cnt[maxn];
bool has_edge[maxn][maxn];
bool can[maxn];
int n,m,all; void get_edge() {
for(int i=;i<all;i++) if((i&i>>)==)
{
can[i]=true;
for(int j=;j<n;j++) if(i&(<<j)) cnt[i]++;
for(int j=;j<all;j++)
if(((i&j)==) && ((i>>)&j)== && ((j>>)&i)==)
has_edge[i][j]=true;
}
} int main() {
cin>>n>>m;
all=<<n; get_edge();
for(int s=;s<all;s++) if(can[s]) d[][s][cnt[s]]=; for(int i=;i<=n;i++)
for(int s1=;s1<all;s1++) if(can[s1])
for(int j=cnt[s1];j<=m;j++)
{
for(int s2=;s2<all;s2++) if(can[s2] && has_edge[s1][s2])
d[i][s1][j] += d[i-][s2][j-cnt[s1]];
}
LL ans=;
for(int s=;s<all;s++) ans += d[n][s][m];
cout<<ans;
return ;
}
另外一定要注意二进制的运算优先级，不确定的时候就加括号。