今日总结2024/5/27

今日学习了状态压缩DP,状态压缩DP分为棋盘型(基于连通性)和集合型

Acwing.1064 小国王

在 n×n的棋盘上放 k个国王，国王可攻击相邻的 8个格子，求使它们无法互相攻击的方案总数。

输入格式
共一行，包含两个整数 n和 k。

输出格式
共一行，表示方案总数，若不能够放置则输出0。

数据范围
1≤n≤10,
0≤k≤n^2

每一行的状态都由上一行来决定，因此要分别枚举上一行状态和下一行状态来判断是否能合法转移，再进行计算，因此要将能合法转移的状态进行预处理，（a&b）==0代表二者不能出现在同一列,a|b不能出现连续的1代表二者不能不能出现在相邻的列

#include <bits/stdc++.h>
using namespace std;
//把一堆方案归类成一类来划分集合
//int f[i][j][s] 前i行放完，放了j个棋子,最后一行状态为s(二进制)属性为count方案数
const int N=12,M=1<<10,K=110;
int n,m,cnt[M];
long long f[N][K][M];//要开longlong不然会爆int
vector<int> h[M];
vector<int> state;bool check(int u){for(int i=0;i<n;i++)if((u>>i&1)&&((u>>i+1)&1))return false;return true;
}int count(int u){int res=0;for(int i=0;i<n;i++)if(u>>i&1) res++;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);}for(int i=0;i<state.size();i++)for(int j=0;j<state.size();j++){int a=state[i],b=state[j];//处理好i-1到i的映射关系if((a&b)==0&&check(a|b))h[i].push_back(b);//一定要是下标映射，不同方案的十进制可能相等}f[0][0][0]=1;for(int i=1;i<=n+1;i++)for(int j=0;j<=m;j++)for(int k=0;k<state.size();k++){int a=state[k],c=cnt[a];for(auto b:h[k])if(j>=c)//一定要大于放的f[i][j][a]+=f[i-1][j-c][b];}cout<<f[n+1][m][0];//第n+1行的状态为0return 0;
}