bzoj1087[SCOI2005]互不侵犯King

bzoj1087[SCOI2005]互不侵犯King

​​ Description 　　在N×N的棋盘里面放K个国王，使他们互不攻击，共有多少种摆放方案。国王能攻击到它上下左右，以及左上 左下右上右下八个方向上附近的各一个格子，共8个格子。

Input 　　只有一行，包含两个数N，K （ 1 <=N <=9, 0 <= K <= N * N）

Output 　　方案数。

Sample Input 3 2 Sample Output 16 提前预处理出我两个状态之间是否可以摆放 提前预处理出我这一行这种状态能否摆放 然后我就可以开始dp了 设方程f[i][j][s]表示我现在在第i行 现在已经摆放j个人然后我第i行的状态是s我逐行递推 首先枚举我当前这一行有多少状态可以摆放 再枚举上一个状态有多少情况可以摆放 再判断这两个是否真的可以摆放 然后枚举已经摆放的总人数 从上一行的人数枚举到总人数-我当前这一行的人数 表示我截至上一行的状态我一共已经摆放了多少个了 然后我再把这种情况给累加到我当前这一行的合法状态中即可

#include#define N 600long long f[11][120][600];int n,k,bin[10],num[N];bool flag[N],mp[N][N];int main(){// freopen("bzoj1087.in","r",stdin); scanf("%d%d",&n,&k);for (int i=0;i<=n;++i) bin[i]=1<=0;--s){ if ((s&(s>>1))) continue; int tmp=0;for (int j=0;j=0;--s){ if (!flag[s]) continue; for (int s1=bin[n]-1;s1>=0;--s1){ if (!flag[s1]) continue;if ((s1&s)||(s&(s1>>1))||(s1&(s>>1))) continue; mp[s][s1]=1; } } for (int s=0;s<=(bin[n]-1);++s) if (flag[s]) f[1][num[s]][s]=1; for (int i=2;i<=n;++i){ for (int s=0;s<=bin[n]-1;++s){//表示我当前这一行的状态 if (!flag[s]) continue; for (int s1=0;s1<=bin[n]-1;++s1){//表示我前一行的状态 if (!mp[s1][s]||!flag[s1]) continue; for (int j=num[s1];j<=k-num[s];++j){//枚举我当前所有可能的人数 f[i][j+num[s]][s]+=f[i-1][j][s1]; } } } }long long ans=0; for (int s=0;s<=(bin[n]-1);++s) ans+=f[n][k][s]; printf("%lld",ans); return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。