[SCOI2005]互不侵犯King

2019-11-08 03:17:42

字體：大中小

供稿：網(wǎng)友

https://www.luogu.org/PRoblem/show?pid=1896 感覺像N皇后問題有沒有啊，但是這里范圍比較少，我們可以采用狀壓dp來搞一搞；預處理搞出每一種狀態(tài)需要國王的數(shù)量，以及每兩種狀態(tài)之間是否以銜接，之后用dp一層一層地算就好了現(xiàn)在我知道為什么有人說：黃學長是我們的紅太陽了；

黃學長是我們的紅太陽！！！

#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層，已經(jīng)放了p個，i層狀態(tà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]++;//算位數(shù) 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++)//枚舉層數(shù) 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層狀態(tài)是k，顯然最少個數(shù)是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安裝與基本使用

下一篇：文件壓縮上傳