在?N \times NN×N?的棋盤里面放?KK?個國王，使他們互不攻擊，共有多少種擺放方案。國王能攻擊到它上下左右，以及左上左下右上右下八個方向上附近的各一個格子，共?88?個格子。

輸入格式

只有一行，包含兩個數?N, KN,K。

輸出格式

所得的方案數。

樣例

InputcopyOutputcopy

3 2	16

數據范圍與提示

1 \le N \le 9, 0 \le K \le N \times N1≤N≤9,0≤K≤N×N

#include <bits/stdc++.h> using namespace std; typedef long long ll; int bits[1010],num[1010],cnt,n,m;// dp[][][] : 第幾行 當前狀態 總共一的個數 的方案數 ll dp[10][1100][85]; void dfs(int now,int nu,int s) // s:一的個數 nu:第幾列 now:當前狀態 bits[]:記錄合法狀態 num[]:當前狀態的一個數 {if(nu >= n){cnt++;bits[cnt] = now;num[cnt] = s;return;}dfs(now,nu+1,s);dfs(now+(1<<nu),nu+2,s+1); } int main() {cin >> n >> m;dfs(0,0,0);for(int i = 1;i <= cnt; i++)dp[1][i][num[i]] = 1;for(int i = 2;i <= n; i++){for(int j = 1;j <= cnt; j++){for(int k = 1;k <= cnt; k++){ if(bits[j] & bits[k]) continue;if((bits[j]<<1 & bits[k]) || (bits[j]>>1 & bits[k])) continue;for(int l = num[k]; l <= m; l++){dp[i][k][l] += dp[i-1][j][l-num[k]];}}}}ll ans = 0;for(int i = 1;i <= cnt; i++)ans += dp[n][i][m];cout << ans;return 0; }

總結

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

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