$\huge \color{orange}{成魔之路->}$ $\huge \color{purple}{算法提高课题解}$

思路：

• $1. 状态表示$
  $集合：前\ i\ 行已经摆好，且已摆放好\ j\ 个国王，第\ i\ 行状态是\ a\ 的方案$
  $属性：Count$

• $2. 状态转移$
  $a\ 是第\ i\ 行的状态，b\ 是第\ {i-1}\ 行的状态，b\ 是\ a\ 所能转移的状态$
  $f[i][j][a]\ +=f[i-1][j-cnt[a]][b]$

可参考： 蒙德里安的梦想

完整代码

#include<bits/stdc++.h>

using namespace std;

typedef long long LL;

const int N = 12, M = 1 << 10, K = 110;

int n,m;
int cnt[M]; //记录该状态中 1 的个数，即该状态所能摆放的国王个数
LL f[N][K][M]; //前 i 行已经摆好，且已摆放好 j 个国王，第 i 行状态是 a 的方案
vector<int> state; //合法的状态
vector<int> head[M]; //该状态能够转移的状态

//判断该状态是否有相邻的 1，若没有则合法
bool check(int state)
{
    return !(state&state>>1);
}

//统计该状态中 1 的个数
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))
        {
            state.push_back(i);
            cnt[i]=count(i); //记录该状态中 1 的个数
        }

    //枚举出该状态所能转移到的状态
    for(int i=0;i<state.size();i++)
        for(int j=0;j<state.size();j++)
        {
            int a=state[i],b=state[j];
            if(!(a&b)&&check(a|b)) //能够转移的条件
                head[a].push_back(b); //状态 a 和状态 b 之间可互相转移
        }

    f[0][0][0]=1;
    for(int i=1;i<=n+1;i++)
        for(int j=0;j<=m;j++)
            for(auto a : state) //枚举第 i 行的状态
                for(auto b : head[a]) //枚举第 i - 1 行的状态
                    if(j>=cnt[a]) 
                        f[i][j][a]+=f[i-1][j-cnt[a]][b]; //状态 a 可由状态 b 转移过来

    // LL res=0;
    // for(auto x : state) res+=f[n][m][x];
    // cout<<res<<endl;
    // 上述代码等价于f[n+1][m][0]
    cout<<f[n+1][m][0]<<endl;

    return 0;
}