在N×N的棋盤裡面放K個國王，使他們互不攻擊，共有多少種擺放方案。國王能攻擊到它上下左右，以及左上左下右上右下八個方向上附近的各一個格子，共8個格子。
只有一行，包含兩個數N，K （ 1 <=N <=9, 0 <= K <= N * N）
方案數。
3 2
16
首先這道題用到了名叫狀壓dp的算法
首先聲明：這篇博客不適用於大神們!!!!!
看到互不侵犯的king這道題首先想到的是八皇後問題，但是發現和八皇後大不一樣，因為八皇後是用的深搜的方法，但是由於根據國象的規則，一個棋盤能放的皇後要比國王少得多，所以DFS即可。
所以我們考慮其他的方法，因為國王的攻擊范圍很小，只有周圍的一圈。但我們依然不能把所有的狀態推出來（即使n<=9）。但我們可以發現只要確定了第一行，就可以將下面的用動規推出來。這樣我們就可以用枚舉的方式來做了。在枚舉的同時，我們可以用二進制的方式來表示狀態，這樣較好比較，同時也可以壓縮狀態，這就是狀壓dp的思想。在這裡可以模擬一下。
比如說n=5。 用1表示該格有國王，0反之。
1 1 1 1 1 這種情況顯然是不存在的，我麼就要把它排除掉。那麼怎麼排除呢？我們考慮用位運算的思想。將它 右移（>>）一位（因為國王的攻擊范圍只有1）。即 1 1 1 1 1再進行（&）運算，這樣的返回值是1則出現沖突，再比如這種情況 1 0 1 0 1 1 1 1 1 1 。 1 0 1 0 1 這樣的返回值是0，所以這種情況存在。而二進制我們可以直接用一個十進制數來表示。如 1 1 1 1 1 十進制是31，可以試一試計算 31&（31>>1）==1.而 1 0 1 0 1 十進制是21，
21&(21>>1)==0。比較時應該左移、右移都進行。另外我們還可以進行預處理。總狀態數為 2^n-1，只進行循環即可，代碼如下
int check2(int a)//一行自比
{
if(a&(a<<1)) return 0;
if(a&(a>>1)) return 0;
return 1;
}
int get(int x)//計算狀態為x，其中 1 的個數。
{
int tot=0;
while(x){
if(x&1)
tot++;
x=x>>1;
}
return tot;
}int tot=(1<<n)-1;
for(int i=0;i<=tot;i++)
if(check2(i)){
zt[++num]=i;//狀態
gs[num]=get(i);//該狀態含的國王的個數
}
接下來講dp的過程——
int f[10] (i) [600] (j) [82] (k) {0};//i為行數，j為第j種狀態，k為當前總國王數 f[i][j][k]表示第i行狀態為第j種放置了k個國王的方案數。
另外的一種預處理如下，對比兩行的狀態，可以加速dp過程中的比較。
int check1(int a,int b)//兩行對比
{
if(a&(b<<1)) return 0;
if(a&(b>>1)) return 0;
if(a&b)return 0;//對比兩行時就需要對比不移動時的狀態，至於為什麼，自行腦補![]()
return 1;
}
for(int i=1;i<=num;i++)//pd[i][j]==1則表示i在上一行j在下一行，並且不沖突
for(int j=1;j<=num;j++)
if(check1(zt[i],zt[j]))
pd[i][j]=pd[j][i]=1;
主要的dp過程如下
for(int i=0;i<n;i++)//循環行數，對應f數組中的行數（i）
for(int j=1;j<=num;j++)//循環狀態，對應f數組中的（j）
for(int k=0;k<=m;k++)//循環國王數，對應數組中的（k）
if(f[i][j][k])
for(int q=1;q<=num;q++)//循環i下一行的狀態
if(pd[j][q]&&(k+gs[q]<=m))//滿足條件就繼續
f[i+1][q][k+gs[q]]+=f[i][j][k];
long long int ans=0;
for(int i=1;i<=num;i++)//把第n行的所有狀態的f值相加即為答案
ans+=f[n][i][m];
這就是主要的函數，其他的自己加上的吧，光復制標程是沒有意義的！！
注意：f[0][1][0]=1 即初始的狀態。
