蓝桥集训之小国王

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

蓝桥集训之小国王

• 核心思想：状态压缩dp

  • 将每张图对应的上一张符合要求的图存入二维数组
  • 依次取出并更新当前值

•   #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)  //判断当前图是否符合要求 左右不能同为1{for(int i=0;i<n;i++)if((state >> i & 1) && (state>>i+1 & 1))return false;return true;}int count(int state)  //求有多少1{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);}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))h[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<states.size();a++)for(auto b : h[a])  //a和j都从头遍历了一遍{int c = cnt[states[a]];if(j>=c) f[i][j][a] += f[i-1][j-c][b];}cout<<f[n+1][m][0];}
  

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

---