状态压缩动态规划

                     

贡献者: 有机物

   状态压缩是将一个长度为 $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;
}

                     

© 小时科技 保留一切权利