AcWing 1064. 小国王
原题链接
简单
#include <bits/stdc++.h>
using namespace std;
const int N = 20, M = 1 << 10, K = 1e2 + 10;
typedef long long ll;
int n, m;
vector<int> legal_state; // 存储一行所有合法的状态
vector<int> state_trans[M]; // 存储一行每一种合法的状态的合法转移
int cnt[M]; // 记录每一种合法状态二进制表示中1的个数
ll f[N][K][M];
bool check(int state) { // 判断state中是否有连续的1
return !(state & state >> 1);
}
int count(int state) { // 计算state的二进制表示中1的个数
int res = 0;
for (int i = 0; i < n; i++) res += state >> i & 1;
return res;
}
int main() {
scanf("%d%d", &n, &m);
// 预处理legal_state & cnt
for (int i = 0; i < 1 << n; i++)
if (check(i)) {
legal_state.push_back(i);
cnt[i] = count(i);
}
// 预处理state_trans
for (auto a : legal_state)
for (auto b : legal_state)
if (!(a & b) && check(a | b)) // ==的优先级高于& 需要写成(a & b) == 0 或者 !(a & b)
state_trans[a].push_back(b);
// DP
f[0][0][0] = 1;
for (int i = 1; i <= n + 1; i++)
for (int j = 0; j <= m; j++)
for (auto a : legal_state)
for (auto b : state_trans[a])
if (j >= cnt[a]) f[i][j][a] += f[i - 1][j - cnt[a]][b];
printf("%lld", f[n + 1][m][0]);
return 0;
}