题解:首先,这道题可以用位运算来表示每一行的状态,同八皇后的搜索方法,然后对于限制条件不相互攻击,则只需将新加入的一行左右移动与上一行相&,若是0则互不攻击,方案可行。对于每种方案,则用递推来统计,将前一排所有可以的情况全部加上即可。bit数组记录每个数字二进制位中1的个数,方便计算。
if(check(j,q))f[i][j][k]+=f[i-1][q][k-bit[j]];
#include <iostream> #define rep(i,n) for (int i=0;i<n;i++) using namespace std; int n,m,s,bit[515]; bool ok[515]; long long f[10][515][85],ans=0; bool check(int p,int q){return((p&q)==0)&&(((p>>1)&q)==0)&&(((p<<1)&q)==0);} int main(){ cin>>n>>m; s=(1<<n)-1; rep(i,s)if((i&(i>>1))==0){bit[i]=__builtin_popcount(i);f[1][i][bit[i]]=1;ok[i]=1;} for(int i=2;i<=n;i++)rep(j,s)if(ok[j]) for(int k=bit[j];k<=m;k++)rep(q,s)if(check(j,q))f[i][j][k]+=f[i-1][q][k-bit[j]]; rep(j,s)ans+=f[n][j][m]; cout<<ans; return 0; }
BZOJ 1087 互不侵犯King (位运算),布布扣,bubuko.com
原文:http://www.cnblogs.com/forever97/p/bzoj1087.html