原题链接 https://www.acwing.com/problem/content/1066/
题目:
在 n×n的棋盘上放 k 个国王,国王可攻击相邻的 8个格子,求使它们无法互相攻击的方案总数。
思路:
每一行的方案数只跟上一行的方案数有关,满足无后向性;
但是状态转移比较复杂,只能枚举,因此用状压dp;
y总用了下标转移,感觉不用也行,只需预处理和转移的时候一致就行
代码:
#include<bits/stdc++.h>
using namespace std;
const int N = 12, S = (1 << 10) + 5, K = 102;
typedef long long ll;
ll f[N][K][S];
vector<int> state, head[S];
#define count(x) (__builtin_popcount(x))
//判断不能有两个连续1的状态
inline bool check(int x){
return !(x&(x >> 1));
}
int main(){
int n , k;
cin >>n >> k;
//预处理,统计所有的合法状态
for(int i = 0; i < 1 << n; i++){
if(check(i)) {
state.push_back(i);
}
}
//预处理,统计状态可转移的上个状态
for(int i = 0; i < state.size(); i++){
for(int j = 0; j < state.size(); j++){
int a = state[i], b = state[j];
if( (a&b) == 0 && check(a | b)) head[a].push_back(b); // 位运算记得加括号
}
}
f[0][0][0] = 1;// 初始转太
for(int i = 1; i <= n+1; i++){ //枚举行
for(int j = 0; j <= k; j ++){ //枚举放置个数
for(int x = 0; x < state.size(); x++){//枚举这行的合法状态
int a = state[x];
int c = count(a);
if( j >= c)
for(auto b: head[a]){ //枚举上一行的合法状态
f[i][j][a] += f[i-1][j-c][b];
}
}
}
}
cout << f[n+1][k][0];
return 0;
}