#2153. 「SCOI2005」互不侵犯(状压DP)

#2153. 「SCOI2005」互不侵犯

解题思路
令dp[i][j][k]表示第i行的状态为j时，共放置k个国王的方案数。
状态j的二进制即表示该行的放置方式，例如j为3时，放置的方式为101，即从右向左看第一位和第三位放置国王，其他位不放置。
可以预处理出每一行所有的合法状态，即两两不相邻的状态。
然后在相邻两层枚举所有合法状态，若这两层也不发生冲突，进行转移即可。
参考代码

#include <bits/stdc++.h>
using namespace std;
const int N = 10;
#define ll long long
int can[(1 << N)], tot;// 记录一行中合法的摆放方案
int cnt[(1 << N)]; // 合法方案数1的个数
ll dp[N + 1][(1 << N)][N * N + 10];
int n, k;
int sum(int x)//状态x中1的个数
{
    int t = 0;
    while (x)
    {
        if (x & 1)
            ++t;
        x >>= 1;
    }
    return t;
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin >> n >> k;
    for (int i = 0; i < (1 << n); ++i)//第一层状态要手推，无法转移
    {//注意枚举范围是[0, (1 << n) - 1], 因为棋盘只有这么大
        if (!(i & (i << 1)))
        {
            can[tot] = i;
            cnt[tot] = sum(i);
            dp[1][i][cnt[tot++]] = 1;
        }
    }
    for (int i = 2; i <= n; ++i)
    {//层数
        for (int j = 0; j < tot; ++j)
        {//当前层状态
            for (int a = 0; a < tot; ++a)
            {//上一层状态
                int x = can[j], y = can[a];
                if (x & y || (x << 1) & y || (x >> 1) & y)
                    continue;//状态冲突则跳过
                for (int b = cnt[j]; b <= k; ++b)
                {//枚举国王个数
                    dp[i][x][b] += dp[i - 1][y][b - cnt[j]];
                }
            }
        }
    }
    ll ans = 0;
    for (int i = 0; i < tot; ++i)
    {
        ans += dp[n][can[i]][k];
    }
    cout << ans << endl;
    return 0;

}