首页 > 代码库 > P1896 [SCOI2005]互不侵犯King
P1896 [SCOI2005]互不侵犯King
题目描述
在N×N的棋盘里面放K个国王，使他们互不攻击，共有多少种摆放方案。国王能攻击到它上下左右，以及左上左下右上右下八个方向上附近的各一个格子，共8个格子。
输入输出格式
输入格式：
只有一行，包含两个数N，K （ 1 <=N <=9, 0 <= K <= N * N）
输出格式：
所得的方案数
输入输出样例
输入样例#1：
3 2
输出样例#1：
状压dp
16
题解：状态压缩动规，用一个整型的二进制表示来表示棋盘上一行的情况，放了棋子为1，没放为0；可以先预处理出所有可能的状态；用位运算来判断两种状态能否共存于相邻两行。（表示位运算看的有点蒙蔽）。
#include<iostream>#include<cstdio>using namespace std;int n,k,i,j,k1,all,f[9][26][512],cnt[512],p;bool f1[512],f2[512][512];long long ans;void xx(){ int t,x; for(;i<all;i++) if((i&(i>>1))==0) { for(t=0,x=i;x;x/=2)t+=x&1; cnt[i]=t; f1[i]=true; } for(i=0;i<all;i++) if(f1[i]) for(j=0;j<all;j++) if(f1[j]) if((i&j)==0&&(i&(j>>1))==0&&(j&(i>>1))==0) f2[i][j]=true;}int main(){ scanf("%d%d",&n,&k); if(k>(n+1)/2*(n+1)/2) { cout<<0<<endl; return 0; } all=1<<n; xx(); for(i=0;i<all;i++) f[0][cnt[i]][i]=1; for(i=1;i<n;i++) for(j=0;j<all;j++) if(f1[j]) for(k1=0;k1<all;k1++) if(f2[j][k1]) for(p=cnt[j];p+cnt[k1]<=k;p++) f[i][p+cnt[k1]][k1]+=f[i-1][p][j]; for(i=0,n--;i<all;i++)ans+=f[n][k][i]; cout<<ans; return 0;}
P1896 [SCOI2005]互不侵犯King
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。