首页 > 代码库 > 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;}
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。