算法提高之小国王

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