状态压缩动态规划

贡献者：有机物

　　状态压缩是将一个长度为 $n$ 的布尔数组用一个长度为 $n$ 的二进制数表示的方法。状态压缩动态规划即为将状态用一个二进制数保存起来，从而可以减少空间开销。存储状态一般是用 int 类型存储，用位运算进行状态计算。简单来讲就是十进制存储状态，二进制表示状态。讲状压 $d p$ 之前首先要学习位运算。

　　位运算的基本操作：异或 xor、与 and、或 or、左移 <<、右移 >>。

　　 ^ 异或预算，若 $x$ 和 $y$ 双方都为 $1$ （TRUE），与操作之后的结果为 $0$ ，若其中一方为 $0$ ，则答案为 $1$ ，所以异或运算也称不进位加法。

　　 1011 ^ 1100 = 111。

　　 & 与运算，若 $x$ 和 $y$ 双方都为 $1$ ，与操作之后的结果才为 $1$ ，否则为 $0$ 。

　　 1011 & 1100 = 1000。

　　 |（回车下面那个键）或运算，只要 $x$ 和 $y$ 一方为 $1$ 答案为 $1$ ，双反都为 $0$ 答案才是 $0$ 。

　　 1000 or 1011 = 1011。

　　 << 左移运算，把二进制数向左移，高位越界后舍弃，低位补 $0$ 。1 << n = 2^n, n << 1 = 2n。

　　 1011 << 2 = 101100。

　　 >> 右移运算，把二进制数向右移，高位以符号位填充，低位越界后舍弃。n >> 1 = n / 2.0。

　　 1011 >> 2 = 10。

图 1：状态压缩位运算常用操作

　　例题一：互不侵犯。

　　题目大意：在 $N \times N$ 的棋盘里面放 $K$ 个国王，使他们互不攻击，共有多少种摆放方案。国王能攻击到它上下左右，以及左上左下右上右下八个方向上附近的各一个格子，共 $8$ 个格子。

　　对于每一行的状态，使用一个 $n$ 位的二进制数来存储每行放国王的状态，比如第一行第一列和第三列放了国王，二进制表示下那一列就为一，没放就为零。每一行有 $2^{n}$ 种不同的状态，分别对应 $2^{n}$ 个二进制数，但合法的状态的数量很少。

　　放国王的约束条件：

同一行内不能摆放国王。
两条对角线也不能摆放相邻的国王。

　　首先预处理出每行合法的状态，记 $s_{i}$ 为第 $i$ 行的状态（合法的摆法）。 $c n t_{i}$ 表示状态为 $i$ 的 $1$ 的个数（即摆的国王的数量）。判断一行内有没有相邻的国王：如果 !(x & x >> 1) 为真，则状态 $i$ 合法，即相邻的位置没有摆放国王。例如 $i = 6_{(10)}, i = 110_{(2)}$ ，右移一位就为 $011_{(2)}$ ，与它做与运算，为真，取反之后就为假，说明 $i = 6$ 这个状态不合法。

　　预处理完之后就可以做状压 $d p$ 了。

　　 状态表示： $f (i, j, k)$

集合：表示从前 $i$ 行摆，且已经摆了 $j$ 个国王，并且当前摆的第 $i$ 行的状态是 $k$ 的集合。
属性：摆放国王的数量的最大值。

　　 状态计算：

　　当前状态答案只和上一行的状态有关系， $a$ 为第 $i$ 行的状态， $b$ 为第 $i - 1$ 行的状态，想要从第 $i - 1$ 行转移到第 $i$ 行，必须得满足当前放到国王的数量要大于等于第 $i$ 行放的国王的数量，还必须得满足上面的两个约束条件，若两个条件都满足，即可进行状态转移：因为求的是方案数，所以从第 $i - 1$ 行到第 $i$ 行累加即可。f(i, j, s[a]) += f(i - 1, j - cnt_z[a], s[b])。

bool check(int a, int b)    // 判断两行之间是不是满足条件
{
    if (!(s[a] & s[b]) && check2(s[a] | s[b]))  // 首先同一列不能有，再就是同一对角线也不能有相邻的国王
        return true;
    return false;
}

　　预处理 $f (0, 0, 0) = 1$ ，因为什么都不放也是一种方案。

　　 时间复杂度： $O (n \times m \times S \times X)$ 。

　　最坏情况下的计算量为： $n = 10, m = 100$ ， $S$ 为合法的状态数量， $X$ 为每个状态的合法数量，两者最坏情况下都为 $10^{3}$ ，整个计算下来约为 $10^{9}$ ，但合法状态并不多，因此不会超时。

const int N = 12, M = 1 << 10, K = 110;
int n, m, cnt, s[1 << N], cnt_z[M];
long long f[N][K][M];

bool check2(int x)  // 判断当前行有没有相邻的国王
{
    return !(x & x >> 1);
}

bool check(int a, int b)     // 判断两行之间是不是满足条件
{
    // 首先同一列不能有，再就是同一对角线也不能有相邻的国王
    if (!(s[a] & s[b]) && check2(s[a] | s[b]))
        return true;
    return false;
}

// 统计 s 的二进制表示下 1 的个数
int count(int s)
{
    int res = 0;
    for (int i = 0; i < n; i ++ ) res += s >> i & 1;
    return res;
}

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

    // // 枚举每一行的合法状态
    for (int i = 0; i < (1 << n); i ++ )    
        if (check2(i))
        {
            s[cnt ++ ] = i;  // 保存每一行的合法状态
            cnt_z[i] = count(i);    // 保存当前合法状态的国王数量
        }

    // 合法的状态数
    // for (int i = 0; i < cnt; i ++ )
    //     cout << i << ' ' << s[i] << ' ' << cnt_z[s[i]] << endl;

    f[0][0][0] = 1; // 什么都不放也是一种方案
    
    for (int i = 1; i <= n + 1; i ++ )  // 枚举行
        for (int j = 0; j <= m; j ++ )  // 枚举国王数
            for (int a = 0; a < cnt; a ++ )  // 枚举第 i 的合法状态
                for (int b = 0; b < cnt; b ++ )  // 枚举第 i - 1 行的合法状态
                {
                    // 第 i 行第 a 个状态的国王数量
                    int c = cnt_z[s[a]];
                    if (j >= c && check(a, b)) 
                        f[i][j][s[a]] += f[i - 1][j - c][s[b]];
                }

    // 枚举到第 n+1 行就相当于计算最后的状态的数量
    cout << f[n + 1][m][0] << endl;
    return 0;
}

致读者：小时百科一直以来坚持所有内容免费无广告，这导致我们处于严重的亏损状态。长此以往很可能会最终导致我们不得不选择大量广告以及内容付费等。因此，我们请求广大读者热心打赏 ，使网站得以健康发展。如果看到这条信息的每位读者能慷慨打赏 20 元，我们一周就能脱离亏损，并在接下来的一年里向所有读者继续免费提供优质内容。但遗憾的是只有不到 1% 的读者愿意捐款，他们的付出帮助了 99% 的读者免费获取知识，我们在此表示感谢。