acwing 1064 小国王线性状态压缩DP

news/2024/10/17 12:37:00/

在这里插入图片描述
输入

3 2

输出

🍺 AC code

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<vector>using namespace std;typedef long long ll;
const int N = 12;
const int M = 1 << 10, K = 110;//k表示国王数
int n,m;
vector<int> state;//存储所有单行合法状态
int id[M];//存的是每一个状态和这个它的下标之间的对应关系
vector<int> head[M];//记录每个状态可以转到哪些其他的状态
int cnt[M];//记录状态 i 里边 1 的个数ll f[N][K][M];bool check(int state)
{for(int i = 0; i < n; i++)if((state >> i & 1) && (state >> (i + 1) & 1))return false;return true;
}
// 计算 state 二进制 里边有多少个 1
int count(int state )
{int res = 0;for(int i = 0; i < n; i++)res += state >> i & 1;return res;
}int main(){cin >> n >> m;// n是 棋盘边长,m是 国王个数//	预处理单行合法状态for(int i = 0; i < 1 << n; i++)if(check(i)){state.push_back(i);id[i] = state.size()-1;//id存的是 状态 i 所对应的state下标cnt[i] = count(i); 		}//	预处理状态之间是否可以转移（即上一行状态和下一行状态是否冲突）for(int i = 0; i < state.size(); i++)// i是当前状态的下标for(int j = 0; j < state.size(); j++)// j 是下一个状态的下标{int a = state[i];int b = state[j];
//			没有冲突的1			没有连续的两个 1if((a & b) == 0 && check(a | b))//合法head[i].push_back(j);//表示 i 下边可以接 j}//	开始DPf[0][0][0] = 1;for(int i = 1; i <= n+1; i++)// i 表示行数for(int j = 0; j <= m; j++)// j 表示国王数for(int a = 0; a < state.size(); a++)// a 表示第 i 行状态的下标for(int b = 0; b < head[a].size(); b++)// b 表示第 i+1 可能转移到的状态{int c = cnt[state[a]];//c 记录 第i行状态 state[a]中 1 的个数
//			第 i 行采取k状态表示 会 放置 c 个国王，当前状态 f[i][j][k] 表示前i层放置了 j 个国王
//			所以 c 的上限是 jif(j >= c)f[i][j][a] += f[i-1][j-c][head[a][b]];}cout << f[n+1][m][0] << endl;return 0;
}