题解 | #[SCOI2005]互不侵犯KING#
[SCOI2005]互不侵犯KING
https://ac.nowcoder.com/acm/problem/20240
本题需要在N*N个棋盘里面摆放上K个国王，国王需要互不侵犯。那么从这个矩阵的角度来看（果断dfs
）（开玩笑的。
）（开玩笑的。
本题使用状压dp去求解，以每一层作为最外层遍历取走，对于每一层来说哪些格子上放的有国王就是1，没有放国王就是0，所以直接采用二进制去表示每一层的状态。
而到某一层为止到底能放多少国王取决于上一层的状态以及自身不能有侵犯发生。故采用二进制的位运算去判断。
最后状态转移方程为：dp[i][j][st[s].first] += dp[i-1][j-st[s].second][st[t].first];
#include <bits/stdc++.h>
using namespace std;
#define int long long
int dp[10][100][1<<9];
pair<int, int> st[1<<9];
int cnt = 0;
int num(int i) {
int ans = 0;
while (i){
if (i&1==1) ans++;
i = (i>>1);
}
return ans;
}
signed main() {
int n, k;
cin>>n>>k;
dp[0][0][0]=1;
//将合法的二进制数打表打出来
for (int i=0;i<(1<<n);i++) {
if ((i&(i<<1))==0) st[cnt++] = make_pair(i, num(i));
}
for (int i=1;i<=n;i++) {
for (int j=0;j<=k;j++) {
for (int s=0;s<cnt;s++) {
if (st[s].second>j) continue;
for (int t=0;t<cnt;t++) {
if (st[s].first&st[t].first) continue;
if (st[s].first>>1&st[t].first) continue;
if (st[t].first>>1&st[s].first) continue;
dp[i][j][st[s].first] += dp[i-1][j-st[s].second][st[t].first];
}
}
}
}
int ans = 0;
for (int t=0;t<cnt;t++) {
ans += dp[n][k][st[t].first];
}
cout<<ans;
return 0;
}
