首页 > 代码库 > BZOJ 1087 【SCOI2005】 互不侵犯King
BZOJ 1087 【SCOI2005】 互不侵犯King
Description
在N×N的棋盘里面放K个国王，使他们互不攻击，共有多少种摆放方案。国王能攻击到它上下左右，以及左上
左下右上右下八个方向上附近的各一个格子，共8个格子。
Input
只有一行，包含两个数N，K （ 1 <=N <=9, 0 <= K <= N * N）
Output
方案数。
智障状压dp题。 fi,j,S表示前i行放了j个国王，最后一行状态为S的方案数。没开long longWA了两发简直智障。
下面贴代码：
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 #include<cmath> 6 #define File(s) freopen(s".in","r",stdin),freopen(s".out","w",stdout) 7 8 using namespace std; 9 typedef long long llg;10 11 int n,k;12 llg f[10][82][1<<10],ans;13 14 int main(){15 File("a");16 scanf("%d %d",&n,&k);17 f[0][0][0]=1;18 for(int i=1;i<=n;i++)19 for(int j=0;j<=k;j++)20 for(int S=0;S<(1<<n);S++)21 if((!((S<<1)&S)) && (!((S>>1)&S))){22 int x=S,nn=0;23 while(x) nn+=(x&1),x>>=1;24 if(nn<=j)25 for(int s=0;s<(1<<n);s++)26 if((!(s&S)) && (!((s<<1)&S)) && (!((s>>1)&S)))27 f[i][j][S]+=f[i-1][j-nn][s];28 }29 for(int S=0;S<(1<<n);S++)30 ans+=f[n][k][S];31 printf("%lld",ans);32 }
BZOJ 1087 【SCOI2005】 互不侵犯King
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。