425 状态压缩DP 小国王【动态规划】

小国王的滚动数组优化没有，我这里贴一下补全。

```C++

#include <iostream>

#include <cstring>

#include <algorithm>

using namespace std;

int n, k;       //棋盘行数，国王总数

int cnt;        //一行的合法状态个数

int s[1 << 9]; //一行的合法状态集

int num[1 << 9]; //每个合法状态包含的国王数

long long f[2][82][1 << 9];// 放0 <= K <= N * N, 0-81//  1 <=N <=9行,11临界

//f[i,j,a]表示前i行已放了j个国王，第i行的第a个状态时的方案数

int main() {

    cin >> n >> k;

    for (int i = 0; i < (1 << n); i++) //枚举一行的所有状态

        if (!(i & i >> 1)) {      //如果不存在相邻的1

            s[cnt++] = i;           //一行的合法状态集，例101

            for (int j = 0; j < n; j++)

                num[i] += (i >> j & 1); //每个合法状态包含的国王数

        }

    f[0 & 1][0][0] = 1;               //边界

    for (int i = 1; i <= n + 1; i++) //枚举行可能编译器检查 i == n + 2

        for (int j = 0; j <= k; j++)  //枚举国王数

            for (int a = 0; a < cnt; a++) { //枚举第i行的合法状态

                f[i & 1][j][a] = 0;// 清空f[i & 1][j][a]为零,避免影响计算

                for (int b = 0; b < cnt; b++) { //枚举第i-1行的合法状态

                    int c = num[s[a]];      //第i行第a个状态的国王数

                    if ((j >= c)            //可以继续放国王

                        && !(s[b]&s[a])       //不存在同列的1

                        && !(s[b] & (s[a] << 1)) //不存在斜对角的1

                        && !(s[b] & (s[a] >> 1)))

                        f[i & 1][j][a] += f[(i - 1) & 1][j - c][b]; //行间转移

                }

            }

    cout << f[(n + 1) & 1][k][0] << endl; //第n+1行不放国王的方案数

    return 0;

}

```