首页 > 代码库 > 互不侵犯King(bzoj 1087)
互不侵犯King(bzoj 1087)
Description
在N×N的棋盘里面放K个国王,使他们互不攻击,共有多少种摆放方案。国王能攻击到它上下左右,以及左上
左下右上右下八个方向上附近的各一个格子,共8个格子。
Input
只有一行,包含两个数N,K ( 1 <=N <=9, 0 <= K <= N * N)
Output
方案数。
Sample Input
3 2
Sample Output
16
/* 一看就是状压DP,而且状态也很好设,dp[i][j][s]表示前i行填了j个国王,第i行的状态是s的方案数。 但是这样直接转移,状态太多,会超时,我们发现,由于不能攻击到相邻的,所以每一行的状态是不多的,可以预处理一下。 */ #include<cstdio> #include<iostream> #define M 600 #define lon long long using namespace std; lon dp[10][100][M]; int map[M][M],stay[M],num[M],m,n,k; void dfs(int s,int last,int t){ stay[++m]=s; num[m]=t; if(t>=k) return; for(int i=last+2;i<=n;i++) dfs(s+(1<<i-1),i,t+1); } int main(){ scanf("%d%d",&n,&k); dfs(0,-1,0); for(int i=1;i<=m;i++) for(int j=1;j<=m;j++) if(stay[i]&stay[j]||((stay[i]<<1)&stay[j])||((stay[i]>>1)&stay[j])) map[i][j]=1; dp[0][0][1]=1; for(int i=1;i<=n;i++) for(int j=0;j<=k;j++) for(int s1=1;s1<=m;s1++){ if(num[s1]>j) continue; for(int s2=1;s2<=m;s2++) if(!map[s1][s2]&&num[s1]+num[s2]<=j) dp[i][j][s1]+=dp[i-1][j-num[s1]][s2]; } lon ans=0; for(int i=1;i<=m;i++) ans+=dp[n][k][i]; printf("%lld",ans); return 0; }
互不侵犯King(bzoj 1087)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。