首页 > 代码库 > 刷题向》关于第一篇状压DP BZOJ1087 (EASY+)
刷题向》关于第一篇状压DP BZOJ1087 (EASY+)
这是本蒟蒻做的第一篇状压DP,有纪念意义。
这道题题目对状压DP十分友善,算是一道模板题。
分析题目,我们发现可以用0和1代表每一个格子的国王情况,
题目所说国王不能相邻放置,那么首先对于每一行是否合法的判断条件就出来了:就是对于情况X,如果X&(x<<1)==0,即为合法情况。
同理这样我们就可以得出每一行对于上一行是否合法的条件:(x&y)==0&&(x&(y<<1))==0&&(x&(y>>1))==0
得出这个结论之后就比较好处理了,枚举行数,当前行情况,上一行情况,以及国王个数情况。
在对于国王的个数的处理时,不能只考虑上一行自己的国王情况,还要考虑在上一行的情况下,还能有多少国王,这点在对于国王个数的处理时解决。
然后给出题目
escription
在N×N的棋盘里面放K个国王,使他们互不攻击,共有多少种摆放方案。国王能攻击到它上下左右,以及左上
左下右上右下八个方向上附近的各一个格子,共8个格子。
Input
只有一行,包含两个数N,K ( 1 <=N <=9, 0 <= K <= N * N)
Output
方案数。
Sample Input
3 2
Sample Output
16
思路已经给出,
于是愉快的贴出代码
1 /************************************************************** 2 Problem: 1087 3 User: PencilWang 4 Language: C++ 5 Result: Accepted 6 Time:28 ms 7 Memory:8828 kb 8 ****************************************************************/ 9 10 #include<stdio.h>11 int n,k,num[1025];12 long long ans,f[10][100][1024];13 bool s[1025];14 int main()15 {16 scanf("%d%d",&n,&k);17 int ass=1<<n;18 for(int i=0;i<ass;i++)19 {20 if((i&(i<<1))==0)21 {22 int x=i,sb=0;23 while(x){sb+=(x&1);x>>=1;}24 num[i]=sb;s[i]=true;25 f[1][num[i]][i]=1;26 }27 }28 for(int i=1;i<n;i++)29 {30 for(int x=0;x<ass;x++)31 {32 if(s[x])33 for(int y=0;y<ass;y++)34 {35 if(s[y])36 {37 if((x&y)==0&&((x>>1)&y)==0&&((x<<1)&y)==0)38 for(int z=num[x];z+num[y]<=k;z++)39 f[i+1][z+num[y]][y]+=f[i][z][x];40 }41 }42 }43 }44 for(int i=0;i<ass;i++)45 {46 ans+=f[n][k][i];47 }48 printf("%lld",ans);49 return 0;50 }51
刷题向》关于第一篇状压DP BZOJ1087 (EASY+)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。