Chtholly Nota Seniorious
題目描述
在N×N的棋盤里面放K個國王咖杂，使他們互不攻擊宫静，共有多少種擺放方案。國王能攻擊到它上下左右柿究，以及左上左下右上右下八個方向上附近的各一個格子邮旷，共8個格子。
輸入輸出格式
輸入格式
只有一行蝇摸，包含兩個數(shù)N婶肩，K （ 1 <=N <=9, 0 <= K <= N * N）
輸出格式
所得的方案數(shù)
輸入輸出樣例
輸入樣例#1
3 2
輸出樣例#1
16
解題思路
很典型的一道狀態(tài)壓縮DP的題，我們只需要枚舉N行中每一行的狀態(tài)即可貌夕，如果此行的狀態(tài)與上一行的狀態(tài)不相沖突即可轉移
故我們維護的狀態(tài)變量即為f[ i ][ j ][ k ]表示在第 i 行放了 j 個國王律歼，此時這一行的狀態(tài)為 k （k 中 1 表示放， 0 表示不放）此時的方案數(shù)
那么我們在狀態(tài)轉移時只需要把上一行可能的狀態(tài)能夠得到的方案數(shù)加起來即可
以下是C++代碼啡专，詳細細節(jié)看注釋
C++代碼
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
ll n,cnt,k;//cnt為一行中最大狀態(tài)
ll f[15][110][1<<9],c[1<<9],ans=0;//c[i]表示在i狀態(tài)下的國王數(shù)
inline ll read(){//快讀不解釋
ll Forca=0,Barca=1;
char c=getchar();
while(c<'0' || c>'9'){
if(c=='-')
Barca=-1;
c=getchar();
}
while(c<='9' && c>='0'){
Forca=Forca*10+(ll)(c-'0');
c=getchar();
}
return Forca*Barca;
}
inline bool check(ll x,ll y){//判斷兩種狀態(tài)是否沖突
if((x&y)!=0) return 0;//狀態(tài)x與狀態(tài)y之間有位置相同的國王险毁，沖突
if((x&(x<<1))>0) return 0;//狀態(tài)x本身有相鄰國王，沖突
if((y&(y<<1))>0) return 0;//狀態(tài)y本身有相鄰國王，沖突
if((x&(y<<1))>0) return 0;//狀態(tài)x中有國王在狀態(tài)y中國王的左下畔况，沖突
if((y&(x<<1))>0) return 0;//狀態(tài)y中有國王在狀態(tài)x中國王的右下鲸鹦，沖突
return 1;//不符合一切沖突條件，即不沖突
}
int main(){
n=read(),k=read();
cnt=(1<<n)-1;//處理出最大狀態(tài)跷跪，即為2^n-1
for(int i=1;i<=cnt;i++)
c[i]=c[i>>1]+(i&1);//預處理c馋嗜，位運算加速
f[0][0][0]=1;
for(int i=1;i<=n;i++)
for(int j=0;j<=cnt;j++)//j為本行狀態(tài)
for(int t=0;t<=cnt;t++)//t為上一行狀態(tài)
if(check(j,t)){//兩個狀態(tài)不相沖突即可轉移
for(int cc=c[j]+c[t];cc<=k;cc++)//枚舉可能放的國王數(shù)
f[i][cc][j]=f[i][cc][j]+f[i-1][cc-c[j]][t];
}
for(int i=0;i<=cnt;i++)
ans+=f[n][k][i];
//把總共n行中共放了k個國王時所有可能的狀態(tài)能夠取到的方案加和即為答案
cout<<ans<<endl;
return 0;
}
