- 专题三 状态压缩dp
小国王
- @ 2025-8-8 15:52:29
#include<bits/stdc++.h>
using namespace std;
const int N = 15, M = 110, K = 1 << 11;
typedef long long LL;
int n, m;
vector<int> head[K], state;
//head[i]存放下标为i的状态所能转移到的状态下标
//state 存放合法的状态
int cnt[K]; //存放每个状态下的国王个数
LL f[N][M][K];
bool check(int x) //判断是否有相邻的1
{
return !(x & x >> 1);
}
int count(int x)
{
int res = 0;
for(int i = 0; i < n; i++)
res += (x >> i & 1);
return res;
}
int main()
{
cin >> n >> m;
for(int i = 0; i < 1 << n; i++)
if(check(i))
{
state.push_back(i);
cnt[i] = count(i);
}
/*预处理2: 所有合法状态的转移过程*/
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[i].push_back(j);
}
}
f[0][0][0] = 1;
for(int i = 1; i <= n + 1; i++)
for(int j = 0; j <= m; j++) //枚举国王个数
for(int a = 0; a < state.size(); a ++) //枚举所有的合法状态
{
for(int b : head[a]) {//合法状态能转移的合法状态
int num = cnt[state[a]];
if(j >= num)
{
f[i][j][a] += f[i - 1][j - num][b];
}
}
}
cout << f[n + 1][m][0];
return 0;
}
/*
f[i][j][k]: 前i层棋盘,放置了j个国王,且第i层状态时k的方案
f[i][j][k] += f[i - 1][j - cnt[k]][pre_k];
sum(f[n][K][所有合法状态])
*/
0 条评论
目前还没有评论...