状态压缩DP

XyzL · 2021-10-01 17:14:26 · 个人记录

前置知识：

1：基础DP

2：位运算的运用

何为状态压缩DP？

状态压缩 DP ，简称状压 DP，是通过一系列操作（使用二进制下的位运算），来将复杂的状态压缩成简单的数字，然后进行转移。

位运算

• 与运算 &（and）：相同位，有 0 为 0，其余为 1 。
• 或运算 |（or）：相同位，有 1 为 1，其余为 0 。
• 异或运算 ^（xor）：相同位，不同为 1 ，相同为 0 。
• 取反操作 ~（not）：0 变 1， 1 变 0 。
• 左移操作 <<（shi）：a << b 是把二进制数 a 向左（高位）移 b 位（低位的最后 b 位补 0 ）。
• 右移操作 >>（shr）：a >> b 是把二进制数 a 向右（低位）移 b 位（高位的起始 b 位补 0 ）。

常用的位运算操作

• 取出二进制数 x 的第 k 位，存在 y 中：y = 1 << k & x（ 或 y = x >> k & 1 ）
• 取出二进制数 x 的最后一个 1 （也就是 lowbit），存在 y 中：y = x & -x
• 将二进制数 x 的第 k 位变为 1 ：x = x | 1 << k
• 将二进制数 x 的第 k 位变为 0 ：x = x & ~ (1 << k)
• 将二进制数 x 的第 k 位取反：x = x ^ 1 << k
• 取出二进制数 x 的最后 k 位，存在 y 中：y = x & （1 << k）- 1
• 将二进制数 x 低位连续的 1 变为 0 ：x = x & x + 1
• 将二进制数 x 低位连续的 0 变为 1 ：x = x | x - 1
• 取出二进制数 x 低位连续的 1 ，存在 y 中：y =(x ^ x + 1)>> 1
• 快速枚举集合 S（用二进制数 x 表示）的所有子集：for(i = x;i != 0;i = (i - 1) & x))

如何应用？

LG1879 [USACO06NOV]Corn Fields G

题意：

给定一片牧场，分成 M 行 N 列，每块土地分为肥沃与贫瘠两种，只能在肥沃的土地种草，且每块草地不可相邻，求种植的总方案数。

分析：

我们可以使用二进制来表示状态， 1 代表种， 0 代表不种。

同时，我们令 f[i][j]，表示在前 i行中（包括 i ）在 j 个状态下的最大方案数。

状态转移方程则为 f[i][j] = (f[i][j] + f[i - 1][k]) mod p。

答案即为：所有的 f[m][i] 。

那么我们如何求所有满足条件的 k ？

根据题意，

显然，贫瘠的土地无法种草。所以我们可以预处理所以肥沃的土地，通过位运算将其标记为 1 。

其次，相邻的土地无法种草。而相邻分为左右和上下两种，我们可以在转移的时候进行判断。

代码：

#include <bits/stdc++.h>

using namespace std;

typedef unsigned long long uLL;

const int MaxSize = 20;

char buf[1 << MaxSize], *p1, *p2;

#define GetChar() \
    ((p1 == p2) ? (p2 = buf + fread(p1 = buf, 1, 1 << MaxSize, stdin), p1 == p2 ? EOF : *p1++) : *p1++)

template <class T>
inline void in(T &x) {
    x = 0;
    register bool f = 0;
    register char c = GetChar();
    while (c < 47 || c > 58) {
        f |= (c == '-'), c = GetChar();
    } 
    while (c > 46 && c < 59) {
        x = (x << 3) + (x << 1) + (c & 15), c = GetChar();
    }
    x = f ? (~x + 1) : x;
}

const int Mod = 1e8;

int m, n, Maxi, Ans, soil[15], f[15][1 << 15];

int main() {
    in(m), in(n);
    Maxi = (1 << n) - 1; // 上线 
    for (register int i = 1; i <= m; ++i) 
        for (register int j = 1; j <= n; ++j) {
            int x;
            in(x);
            soil[i] = (soil[i] << 1) + x; // 预处理 
        }
    f[0][0] = 1; // 边界条件 
    for (register int i = 1; i <= m; ++i) {
        for (register int j = 0; j <= Maxi; ++j) {
            if ((j & (j << 1)) != 0) // 左右相邻 
                continue ;
            if ((j & soil[i]) != j) // 肥沃 or 贫瘠 
                continue ;
            for (register int k = 0; k <= Maxi; ++k)
                if ((k & j) == 0) // 上下相邻 
                    f[i][j] = (f[i][j] + f[i - 1][k]) % Mod;
        }
    }
    for (register int i = 0; i <= Maxi; ++i)
        Ans = (Ans + f[m][i]) % Mod;
    printf("%d\n", Ans);
    return 0;
}

LG1896 [SCOI2005]互不侵犯

题意：

给定一个长度为 n 的正方形棋盘，要求放置 k 个国王，且国王周围八个方向不可有其他国王存在，求摆放的总方案数。

分析：

由题，可以发现，