状压dp

思路很明显，但是实现起来对我来说真难。

这里我就解读一下代码

首先我们定义了一个dp数组
dp[i][j][k]
表示，第i个状态,再第j行，之后要放置k个国王
从第一行开始遍历

我们定义状态为，如果该位为1那么这一行中，我们在这里放置了一个国王
否则我们不放置国王

我们可以先跑一下，预先把所有满足条件的状态都筛选出来
即，01间隔的二进制串，筛选函数pre()，判断非常简单
我们将筛选过的状态存在s数组里

然后下一步，我们开始枚举状态
我们从第一行开始枚举，然后枚举这一行的状态，枚举这一行之后要放置的国王

然后我们要进行状态转移了！！
我们同样开始枚举所有的状态，然后判断两个状态是否冲突。判断冲突的方法和pre()
中相似
ok

注意初始化dp[1][0][0]=1

ok

#include<iostream>
#include<algorithm>
#include <ctime>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
int N, K;
ll f[1 << 10][12][12 * 12];
int s[1 << 10];
int s0 = 0;
void pre() {
    for (int i = 0;i < (1<<N);++i) {
        if (i & (i << 1))continue;
        s[++s0] = i;
    }
}
void dp() {
    f[1][0][0] = 1;
    for (int i = 1;i <= N;++i) {
        for (int t = 1;t <= s0;++t) {
            for (int k = __builtin_popcount(s[t]);k <= K;++k) {
                for (int j = 1;j <= s0;++j) {
                    if ((s[j] & s[t]) || ((s[t] << 1) & s[j]) || ((s[t] >> 1) & s[j]))continue;
                    f[t][i][k] += f[j][i - 1][k - __builtin_popcount(s[t])];
                }
            }
        }
    }
    ll ans = 0;
    for (int i = 1;i <= s0;++i)ans += f[i][N][K];
    cout << ans << endl;
}


int main() {
    ios::sync_with_stdio(0);
    while (cin >> N >> K)pre(), dp();
}