1592 國(guó)王

練習(xí)狀壓DP…
求使它們無法互相攻擊的方案總數(shù)，動(dòng)態(tài)規(guī)劃，其實(shí)和dfs有點(diǎn)像，類似于n皇后問題
n<=10，數(shù)據(jù)范圍真的是可以了，但是深搜的話，時(shí)間復(fù)雜度會(huì)指數(shù)爆炸一樣，不要想了
因?yàn)閷?duì)于每一個(gè)格子都有放或者不放兩種情況，那么就可以用二進(jìn)制來來優(yōu)化
那么一行的數(shù)據(jù)就濃縮成一個(gè)數(shù)了
怎么設(shè)計(jì)狀態(tài)？
我們要在n×n的棋盤放k個(gè)國(guó)王，那么就用f[i][j][k]表示第i行狀態(tài)是a[j]，目前放了k個(gè)棋子
f[i][j][k]=sum{ i-1，l，k-num[j] }其中l(wèi)枚舉上一行狀態(tài)的變量，num[j]是a[j]是這個(gè)狀態(tài)可以放置國(guó)王數(shù)

#include<iostream> #include<cstdio> #include<algorithm> #include<string> #include<cstring> using namespace std;//那么這道題就轉(zhuǎn)化為從0-13的二進(jìn)制數(shù)中找出有三個(gè)1的數(shù)有幾 typedef long long ll; ll n,k; ll num[1000];//記錄國(guó)王的數(shù)量 ll a[1000]; ll f[300][300][300]; ll ans; ll sum; void sol()//計(jì)算狀態(tài)壓縮 {int cnt=0;for(int i=0;i<(1<<n);i++)//枚舉每一行的狀態(tài){if( i&(i<<1) ) continue;//結(jié)果非0會(huì)有1挨著，不合法cnt=0;for(int j=0;j<n;j++) if((1<<j)&i) cnt++;//記錄1的位置a[++sum]=i; //記錄狀態(tài) num[sum]=cnt;//國(guó)王數(shù)量 } } void dp() {f[0][1][0]=1;//第0行第一位上可以放一個(gè)國(guó)王for(int i=1;i<=n;i++)for(int j=1;j<=sum;j++)//枚舉國(guó)王 for(int kk=0;kk<=k;kk++){if(kk>=num[j])for(int l=1;l<=sum;l++)if(!(a[l]&a[j]) && !(a[l]&(a[j]<<1)) && !(a[l]&(a[j]>>1)))//判斷沖突f[i][j][kk]+=f[i-1][l][kk-num[j]]; //放置 }for(int i=1;i<=sum;i++) ans+=f[n][i][k];cout<<ans<<endl; } int main() {cin>>n>>k;sol();dp();return 0; }

總結(jié)

以上是生活随笔為你收集整理的1592 国王的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

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