蓝桥集训之小国王
-
核心思想:状态压缩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]; }