國王

一、題目及數(shù)據(jù)范圍

在n*n的棋盤上放k個國王，國王可攻擊相鄰的8個格子，求使它們無法互相攻擊的方案總數(shù)。
1<=n<=10，0<=k<=n²

二、解法

因為n很小，我們考慮狀壓dp，設dp[i][j][k]表示到第i行，放j個國王，第i行的狀態(tài)為k的方案數(shù)，則有轉移dp[i][j][k]+=dp[i-1][j-cnt][pre]，其中cnt是k中有多少個國王，pre是i-1行的狀態(tài)。我們要確保k和pre不沖突，即判斷二進制下相鄰位存不存在都為1的情況，用位運算即可。

可以發(fā)現(xiàn)每一行的國王都不能相鄰，我們可以預處理出對于一行合法的情況以及對應的國王數(shù)。設fi為一行放到i格的情況數(shù)，考慮放或不放，則有fi=fi-1+fi-2，算的f₁₀=144，比原來需要的2¹⁰次方的枚舉，不知道快了多少。時間復雜度O(n²kf_n²)。

代碼

#include <cstdio> #define LL long long int read() {int x=0,flag=1;char c;while((c=getchar())<'0' || c>'9') if(c=='-') flag=-1;while(c>='0' && c<='9') x=(x<<3)+(x<<1)+c-'0',c=getchar();return x*flag; } int n,N,k,tot,sta[150],cnt[150]; LL dp[11][101][150],ans; int check(int x,int y) {return (!(x&y)) && (!((x<<1)&y)) && (!((x>>1)&y)); } int main() {n=read();k=read();N=(1<<n)-1;for(int i=0;i<=N;i++){if((i<<1)&i || (i>>1)&i) continue;sta[++tot]=i;for(int j=0;j<n;j++)if(i&(1<<j))++cnt[tot];}dp[0][0][1]=1;for(int i=1;i<=n;i++)for(int j=0;j<=k;j++)for(int s=1;s<=tot;s++){if(cnt[s]<=j)for(int p=1;p<=tot;p++){if(j-cnt[s]>=cnt[p] && check(sta[s],sta[p]))dp[i][j][s]+=dp[i-1][j-cnt[s]][p];}}for(int s=1;s<=tot;s++)ans+=dp[n][k][s];printf("%lld\n",ans); }

總結

以上是生活随笔為你收集整理的国王的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。