problem

• 在N×N的棋盤里面放K個(gè)國王
• 每個(gè)國王會(huì)攻擊它周圍的一圈共8個(gè)格子
• 使他們互不攻擊，共有多少種擺放方案
• N <= 9

solution

• 用01串表示某一行放置的情況
• 首先枚舉當(dāng)前做到第幾行，以及當(dāng)前一共放了幾顆棋子。
• 于是狀態(tài)f[i][j][k]表示到第i行，一共放j個(gè)棋子（包括這之前的），且第i行的狀態(tài)是k的方案數(shù)。
• 再考慮轉(zhuǎn)移。這一行肯定是由上一行的狀態(tài)轉(zhuǎn)移過來的，那么我們可以再枚舉上一行的狀態(tài)。
• 很自然的，發(fā)現(xiàn)這會(huì)超時(shí)。每次枚舉一種狀態(tài)就需要2^9，兩重循環(huán)已經(jīng)快爆掉了！我們可以發(fā)現(xiàn)一件事情。比如n=5,我們每次枚舉到的11111,11011,10111,01011這些狀態(tài)都是無效的。那么我們可以先預(yù)處理一下對(duì)于每一行的所有可行的狀態(tài)（就是不能有連續(xù)的1）。
• 這樣的效率仍然不高——我們還可以對(duì)于每種可行的狀態(tài)i,j，預(yù)處理i和j是否能夠相鄰，這樣我們?cè)贒P的時(shí)候，就可以O(shè)(1)來轉(zhuǎn)移了。（這里也可以不預(yù)處理，每次直接判斷ij能否相鄰也可。）

最后，記得開long long。

codes

#include<iostream> using namespace std; const int maxn = 512; typedef long long LL; int c1[maxn], cnt[maxn], c2[maxn][maxn]; LL ans, f[10][100][maxn]; int main(){int n, m;cin>>n>>m;int all = (1<<n)-1;for(int i = 0; i <= all; i++){if((i&(i>>1))==0){c1[i] = 1;for(int x = i; x; x >>= 1) cnt[i]+= (x&1);}}for(int i = 0; i <= all; i++)if(c1[i])f[1][cnt[i]][i] = 1;for(int i = 1; i < n; i++){for(int j = 0; j <= all; j++)if(c1[j]){for(int k = 0; k <= all; k++)if(c1[k]){if(((j&k)==0)&&((j&(k>>1))==0)&&((j&(k<<1))==0)){for(int p = cnt[j]; p+cnt[k]<=m; p++)f[i+1][p+cnt[k]][k] += f[i][p][j];}}}}for(int i = 0; i <= all; i++)ans += f[n][m][i];cout<<ans<<"\n";return 0; }

轉(zhuǎn)載于:https://www.cnblogs.com/gwj1314/p/9444821.html

總結(jié)

以上是生活随笔為你收集整理的【SCOI2005】【BZOJ1087】互不侵犯King（状压dp）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。