首页 > 代码库 > BZOJ 1087 互不侵犯King (位运算)

BZOJ 1087 互不侵犯King (位运算)

题解:首先,这道题可以用位运算来表示每一行的状态,同八皇后的搜索方法,然后对于限制条件不相互攻击,则只需将新加入的一行左右移动与上一行相&,若是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;}