[SCOI2005]互不侵犯King

2019-11-08 03:17:42

字体：大中小

来源：转载

供稿：网友

https://www.luogu.org/PRoblem/show?pid=1896 感觉像N皇后问题有没有啊，但是这里范围比较少，我们可以采用状压dp来搞一搞；预处理搞出每一种状态需要国王的数量，以及每两种状态之间是否以衔接，之后用dp一层一层地算就好了现在我知道为什么有人说：黄学长是我们的红太阳了；

黄学长是我们的红太阳！！！

#include<iostream>#include<cstdio>#define Ll long longusing namespace std;int cnt[1000];bool b[1000][1000],bb[1000];Ll f[10][100][1000];//第i层，已经放了p个，i层状态是j f[i][p][j]int n,m,Max;Ll ans;void hzwer(){ for(int i=0;i<=Max;i++){ int k=i; if(k&(k<<1))continue;//先看看自己本身能不能搞 bb[i]=1; while(k){ if(k&1)cnt[i]++;//算位数 k=k>>1; } } for(int i=0;i<=Max;i++)if(bb[i]) for(int j=0;j<=Max;j++)if(bb[j]) if(i&j||i&(j<<1)||(i<<1)&j);else b[i][j]=1;//看看两两之间能不能搞 }int main(){ scanf("%d%d",&n,&m); Max=1<<n; Max-=1;//这个显然是最二进制n位的大范围 hzwer(); for(int i=0;i<=Max;i++)f[1][cnt[i]][i]=1ll;//先把第一层算好 for(int i=2;i<=n;i++)//枚举层数 for(int j=0;j<=Max;j++)if(bb[j]) for(int k=0;k<=Max;k++)if(bb[k]) if(b[j][k]) for(int p=cnt[k];p+cnt[j]<=m;p++)//i-1层状态是k，显然最少个数是cnt[k] f[i][p+cnt[j]][j]+=f[i-1][p][k];//很显然啊 for(int i=0;i<=Max;i++)ans+=f[n][m][i];//很显然啊 printf("%lld",ans);}

上一篇：memcached安装与基本使用

下一篇：文件压缩上传