首页 > 代码库 > BZOJ 1087: [SCOI2005]互不侵犯King

BZOJ 1087: [SCOI2005]互不侵犯King

2024-08-06 00:37:48   217人阅读

题目

1087: [SCOI2005]互不侵犯King

Time Limit: 10 Sec  Memory Limit: 162 MB

Description

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

Input

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

Output

方案数。

Sample Input

3 2

Sample Output

16

题解

Orz状态压缩动态规划、、、每行之间是有联系的，所以我们按行来推>_< 我写的时候脑子抽了，行与行之间考虑了关系但是忘记了考虑同一行之间的关系，调了好久，简直不能忍、、、

代码

 1 /*Author:WNJXYK*/ 2 #include<cstdio> 3 using namespace std; 4  5 const int MaxB=10; 6 int Pow[MaxB+10]; 7 int FullPow; 8  9 inline void init(int x){10     Pow[0]=1;11     for (int i=1;i<x;i++) Pow[i]=Pow[i-1]<<1;12     for (int i=0;i<x;i++) FullPow+=Pow[i];13 }14 15 inline int lowbit(int x){16     return x&-x;17 }18 19 inline int getDigs(int num){20     int res=0;21     while(lowbit(num)!=0){22         res++;23         num-=lowbit(num);24     }25     return res;26 }27 28 inline bool check(int num){29     int l=lowbit(num);30     num-=l;31     while(lowbit(num)!=0){32         if (lowbit(num)>>1==l) return false;33         l=lowbit(num);num-=l;34     }35     return true;36 }37 38 const int Maxs=1<<10;39 const int Maxn=9;40 const int Maxk=Maxn*Maxn;41 long long f[Maxn+5][Maxk+5][Maxs+5];42 43 int N,K;44 int main(){45     //freopen("In.txt","w",stdout);46     scanf("%d%d",&N,&K);47     init(N);48     //printf("%d\n",getDigs(0));49     for (int sta=0;sta<=FullPow;sta++) if (check(sta))f[1][getDigs(sta)][sta]=1;50     for (int l=2;l<=N;l++){51         for (int prev=0;prev<=FullPow;prev++){52             for (int nxt=0;nxt<=FullPow;nxt++){53                 if (!(nxt&prev) && !((nxt<<1)&prev) && !((nxt>>1)&prev) && check(nxt)){54                     for (int k=getDigs(prev);k<=K;k++){55                         if (k+getDigs(nxt)<=K){56                             f[l][k+getDigs(nxt)][nxt]+=f[l-1][k][prev];57                         }58                     }59                 }60             }61         }        62     } 63     /*64     for (int l=1;l<=N;l++){65         for (int sta=0;sta<=FullPow;sta++){66             for (int k=1;k<=K;k++){67                 if (f[l][k][sta]) printf("%d %d %d -> %d\n",l,sta,k,f[l][k][sta]);68             }69         }70     }71     printf("\n");72     for (int i=0;i<=FullPow;i++)printf("%d %d %d -> %d\n",N,i,K,f[N][K][i]);*/73     long long Ans=0;74         for (int sta=0;sta<=FullPow;sta++){75             Ans+=f[N][K][sta];76         }77     printf("%lld\n",Ans);78     return 0;79 }
没有优化的SB代码

 

BZOJ 1087: [SCOI2005]互不侵犯King


联系
我们