算法提高之小国王

本文主要是介绍算法提高之小国王，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

算法提高之小国王

• 核心思想：状态压缩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;}
  

这篇关于算法提高之小国王的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---