算法提高之小国王
-
核心思想:状态压缩dp
- 先判断每一行是否合法
- 再遍历每一行判断是否和前一行可以组合
- 最后dp
- 状态表示f[i,j,k] = 考虑前 i层的棋盘,前 i层放置了 j个国王,且第 i层状态是 k的方案
- 状态计算 :求和
-
#include<iostream> #include<cstring> #include<algorithm> #include<vector> using namespace std; typedef long long LL; const int N = 15,M = 1<<10,K = 110; LL f[N][K][M]; int n,m; int cnt[M]; vector<int> states; vector<int> h[M]; bool check(int state) { for(int i=0;i<n;i++) if((state>>i & 1) && (state>>i+1 & 1)) return false; return true; } 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; for(int i=0;i<1<<n;i++) //判断单行是否合法 { if(check(i)) { states.push_back(i); cnt[i] = count(i); //同时记录i图中1的数量 } } for(int i=0;i<states.size();i++) //遍历前一行和后一行 { for(int j=0;j<states.size();j++) { int a = states[i],b=states[j]; if((a&b) == 0 && check(a|b)) //a&b没有公共位置 a|b没有斜方向 h[i].push_back(j); } } f[0][0][0] = 1; //初始化 for(int i=1;i<=n+1;i++) //最终到n+1层 且n+1层不放 { for(int j=0;j<=m;j++) //遍历国王数 for(int k=0;k<states.size();k++) //当前状态 for(auto b:h[k]) //取能组合的状态 { int c = cnt[states[k]]; //取国王的数量 if(j>=c) f[i][j][k] += f[i-1][j-c][b]; //当前层放了c个国王 } } cout<<f[n+1][m][0]<<endl; }