状态压缩DP

图中的状态表示不是第i层已经放了j个国王，而是已经放了j个国王

如果直接暴力做的话，会超时，我们需要通过预处理对于每个状态a来说,计算a能从那些合法的状态b转移过来。

$ 时间复杂度O(NKM),空间复杂度O(M^2)$

参考文献

算法提高课

AC代码

#include <iostream>
#include <vector>
using namespace std;


typedef long long LL;
const int N = 12, M = 1 << N , K = 110;

int n , k;
int cnt[M];//记录状态为i的二进制1的个数
vector<int> valid;//记录a | b 是否不存在有连续的两个1的   所有合法状态
vector<int> st[M];//st[a][b]表示，a能被那些合法状态b转移
LL f[N][K][M];


//计算s的二进制位1的个数
int count(int s){
    int res = 0;
    while (s){
        s -= (s & (-s));
        res ++;
    }
    return res;
}

//判断s状态是否合法，即s二进制是否不存在有连续两个1
bool check(int s){
    for (int i = 0 ; i < n ; i ++){
        if ((s >> i & 1) && (s >> (i + 1) & 1))
            return false;
    }
    return true;
}

int main(){
    cin >> n >> k;

    //预处理cnt和valid
    for (int i = 0 ; i < 1 << n ; i ++){
        cnt[i] = count(i);
        if (check(i))
            valid.push_back(i);
    }

    //预处理对于a状态来说，哪些b状态能转移到a
    for (int i = 0 ; i < valid.size() ; i ++){
        for (int j = 0 ; j < valid.size() ; j ++){
            int a = valid[i], b = valid[j];
            if ((a & b) == 0 && check(a | b)) {
                st[a].push_back(b);
            }
        }
    }


    //状态压缩DP
    f[0][0][0] = 1;//初始化
    for (int i = 1; i <= n + 1; i ++ )
        for (int j = 0; j <= k; j ++ )
            //枚举所有合法状态
            for (int u = 0; u < valid.size() ; u ++ )
                //枚举合法状态能被那些状态合法的转移
                for (int v = 0 ; v < st[valid[u]].size() ; v ++){
                    int a = valid[u], b = st[valid[u]][v];
                    int c = cnt[a];
                    if (j >= c)
                        f[i][j][a] += f[i - 1][j - c][b];
                }


    cout << f[n + 1][k][0] << endl;

    return 0;


}