状态压缩动态规划

                     

贡献者： 有机物

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

　　 位运算的基本操作：异或 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$ 个二进制数，但合法的状态的数量很少。

　　 放国王的约束条件：

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

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

　　 预处理完之后就可以做状压 $\tt dp$ 了。

　　 状态表示：$f(i, j, 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$，因为什么都不放也是一种方案。

　　 时间复杂度： $\mathcal{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;
}

                     

© 小时科技 保留一切权利