bitmask 状压DP
Eva.Q Lv9
2022-06-29 14:34:05

”我已经学会了如何活在当下。“

”怎么做？“男孩问。

”找一个安静的地方，闭上眼睛，然后呼吸。“

”听起来真不错，然后呢？“

”然后集中注意力。“

“集中在什么上？”

”蛋糕上。“ 鼹鼠回答。

二进制运算技巧

& ：判断一个数字的二进制表示第 位是否为 if (n & (1 << k))

| ：将数 的第 位置一 n = n | (1 << k)

~ ：所有位都取反

状压DP

Eva学的状压DP，就是用一个二进制数来表示一个集合。

常见的状压DP分为两类，一种是有比较明显的结构的，如图、二维平面坐标等，另一种是较抽象的，比如物品等。

通常来说在压缩状态的基础上，我们还需要一个额外的信息来帮助我们转移，它通常会是关于”最后“的一个信息。

题目

洛谷P1433

题意：在二维平面上给 个点，初始坐标为原点，求遍历所有点的最小距离。

思路：大概就是，比如我现在走到了一个点，我关心的是，有哪些点我还没走过，从当前点往后怎么走最短，我并不关心前面是怎么走的。

设置状态 f[s][id] ，表示我走过了 s 里为 的对应的点，且最后一个点是 id 。我用当前这个状态取更新下一步，也就是说，假设与当前点 id 相连的点是 v ，那么f[s | (1 << v)][v] = min(f[s | (1 << v)][v], f[s][id] + w(id, v)) 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
struct point {
    double x, y;
    inline double sqr(const double &x) {return x * x;}
    inline double dis(const point &obj) {return sqrt(sqr(x - obj.x) + sqr(y - obj.y));}
}c[15];

double f[(1 << 15)][15];

int main() {
    int n; cin >> n;
    for (int i = 0; i < n; ++i) cin >> c[i].x >> c[i].y;
    int S = (1 << n) - 1;
    for (int i = 0; i <= S; ++i)
        for (int u = 0; u < n; ++u) f[i][u] = 1e18;
    point o{0, 0};
    for (int u = 0; u < n; ++u) f[(1 << u)][u] = c[u].dis(o); // 枚举第一个点是谁
    for (int s = 0; s <= S; ++s) // 枚举状态
        for (int u = 0; u < n; ++u) // 枚举最后一个点是谁
            if (s & (1 << u)) { // 判断当前枚举是否合法
                for (int v = 0; v < n; ++v) // 枚举要更新的点
                    if (!(s & (1 << v))) f[s | (1 << v)][v] = min(f[s | (1 << v)][v], f[s][u] + c[u].dis(c[v]));
            }
    double ans = 1e18;
    for (int i = 0; i < n; ++i) ans = min(ans, f[S][i]);
    printf("%.2lf\n", ans);
    return 0;
}

洛谷P1879

给一个二维的矩阵，矩阵里为 的位置不能放东西， 的位置才可以放东西，但放的东西不能相邻（上下左右都不能挨着），问方案数。

思路：压缩行或者列，这里选取压缩行。如果我从上到下一行行考虑，我在考虑第 行的时候，我只关心 行是怎么放的，而不关心再往上的行是怎么放的。对于不能相邻放 这个条件，行内判断挨着可以用 s & (s >> 1) 若结果 则有挨着的位置。考虑相邻的两行，只需要判断 s & s_ ，如果结果 ，则有上下挨着的位置。在转移的过程中，需要枚举当前行的状态和下一行的状态，而每一行的状态是 （），所以如果要枚举两行的状态，其运算量大概在 ，显然，这不行。但我们可以注意到，首先如果一行的状态本身就不合法，那我们就不用再考虑它和别的行拼在一起的情况，并且在 个状态中，一大部分都是非法的，就是有相邻的 ，故为了简化后面的枚举状态，我们预处理出来对于一行来说，哪些状态是合法的，后面枚举的时候，就不用枚举那么多了。

状态设置：f[i][s]，表示当前在处理的是第 行，改行的状态为 s 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#define mod 100000000

int f[13][1 << 12];
vector<int> v; // 存行内可行的状态

int main() {
    int m = rd(), n = rd();
    int S = (1 << n) - 1;
    for (int s = 0; s <= S; ++s)
        if (!(s & (s >> 1))) v.push_back(s);
    f[0][0] = 1;
    for (int i = 1; i <= m; ++i) {
        int sta = 0;
        for (int j = 1; j <= n; ++j) sta = (sta << 1) | rd(); // 读入该行的合法要求
        for (auto s : v)
            if ((s & sta) == s) // s 是 sta 的子集
                for (auto s_ : v) { // 枚举上一行的状态
                    if (!(s_ & s)) f[i][s] = (f[i][s] + f[i - 1][s_]) % mod;
                }
    }
    int ans = 0;
    for (auto s : v) ans = (ans + f[m][s]) % mod; // 对所有情况的方案数求和
    printf("%d\n", ans);
    return 0;
}

又写了一版用当前行更新下一行的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#define mod 100000000

int f[13][1 << 12];
vector<int> v;

int main() {
    int m = rd(), n = rd();
    int S = (1 << n) - 1;
    for (int s = 0; s <= S; ++s)
        if (!(s & (s >> 1))) v.push_back(s);
    f[0][0] = 1;
    for (int i = 0; i < m; ++i) {
        int sta = 0; //下一行的sta
        for (int j = 1; j <= n; ++j) sta = (sta << 1) | rd();
        for (auto s : v) //current line
            for (auto s_ : v) { //next line
                if (!(s_ & s) && (sta & s_) == s_) f[i + 1][s_] = (f[i + 1][s_] + f[i][s]) % mod;
            }
    }
    int ans = 0;
    for (auto s : v) ans = (ans + f[m][s]) % mod;
    printf("%d\n", ans);
    return 0;
}

洛谷P3052

给 个物品和他们各自的体积，限制每组最多放 体积的物品，问最少要分几组。

思路：枚举箱子编号，和哪些物品已经放过了，f[s][i] 表示已经放进箱子的物品的集合是 s ，最后一个箱子为 ，如果这个箱子还放得下，我就放这个箱子，放不下了我就放下一个箱子里。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
int f[1 << 18][18], w[18];

int main() {
    int n = rd(), W = rd();
    for (int i = 0; i < n; ++i) w[i] = rd();
    for (int i = 0; i < (1 << n); ++i)
        for (int j = 0; j < n; ++j) f[i][j] = 1e9;
    f[0][0] = 0;
    int S = (1 << n) - 1;
    for (int s = 0; s <= S; ++s) //当前哪些物品已经放进去了
        for (int k = 0; k < n; ++k) { //箱子编号
            if (f[s][k] == 1e9) continue;
            for (int v = 0; v < n; ++v) { //现在要放的物品
                if (!((1 << v) & s)) {
                    if (f[s][k] + w[v] <= W) f[s | (1 << v)][k] = min(f[s | (1 << v)][k], f[s][k] + w[v]);
                    else f[s | (1 << v)][k + 1] = min(f[s | (1 << v)][k + 1], w[v]);
                }
            }
        }
    int ans = 1e9;
    for (int k = 0; k < n; ++k) {
        if (f[S][k] != 1e9) ans = min(ans, k + 1);
    }
    printf("%d\n", ans);
    return 0;
}

洛谷P4802

有 个点 （）， 条边，在满足不重复访问点的前提下，求以 号点为起点， 号点为终点的最长路径长度。

思路：枚举已访问过的点集，和最后一个访问的点，来更新与该最后一个点相连的点，最终目标就是最后一个点是 。因为起点为 ，所以初态为 f[1][0] = 0; 别的都是负无穷。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
int f[1 << 18][18];
vector<pair<int, int> > V[18];

int main() {
    int n = rd(), m = rd();
    for (int i = 1; i <= m; ++i) {
        int u = rd(), v = rd(), w = rd();
        V[u].push_back(make_pair(v, w));
    }
    int S = (1 << n) - 1;
    for (int i = 0; i <= S; ++i)
        for (int j = 0; j < n; ++j) f[i][j] = -1e9;
    f[1][0] = 0;
    for (int s = 0; s <= S; ++s)
        for (int u = 0; u < n; ++u) {
            if (s & (1 << u))
                for (auto node : V[u]) {
                    int v = node.first, w = node.second;
                    if (!(s & (1 << v))) f[s | (1 << v)][v] = max(f[s | (1 << v)][v], f[s][u] + w);
                }
        }
    int ans = 0;
    for (int s = 0; s <= S; ++s)
        if (s & (1 << (n - 1))) ans = max(ans, f[s][n - 1]);
    printf("%d\n", ans);
    return 0;
}

洛谷P3092

有 个物品， 个硬币，要求顺序购买 个物品，每个物品有自己的价格，硬币不找零，问买完所有的物品后，剩下的钱最多是多少，如果无法购买，输出 。

思路：首先 的范围很大，上界是 ， 的范围比较小，只有 。枚举硬币使用情况的集合，枚举新加进来的硬币是哪个，DP数组记录的就是能买到第几个物品。需要注意的是，因为每一次我们都需要知道在每种情况下，最多能买到第几个物品，如果一个个枚举的话，总体复杂度就是 ，这大概是 ，必然 T。所以在计算最多能买到第几个物品的时候，需要套一个二分。还有就是，因为我们总是关心一个区间里物品的价格和，所以采用前缀和来优化这一子问题。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#define K 16
#define N 100007

int w[K], sum[N], f[1 << K];

inline int find(int L, int R, int limit) { // 找到最多能买到第几个物品
    limit += sum[L - 1]; // sum[R] - sum[L - 1] <= limit 但因为L和R下面会变，但实际上这个式子里的L不应该变，所以在一开始就加到limit里
    while (L < R) {
        int mid = ((L + R + 1) >> 1);
        if (sum[mid] <= limit) L = mid;
        else R = mid - 1;
    }
    return L;
}

inline int solve(int s, int k) { // 计算剩下硬币的价值
    int ans = 0;
    for (int i = 0; i < k; ++i)
        if (!(s & (1 << i))) ans += w[i];
    return ans;
}

int main() {
    int k = rd(), n = rd();
    for (int i = 0; i < k; ++i) w[i] = rd();
    sum[1] = rd();
    for (int i = 2; i <= n; ++i) sum[i] = sum[i - 1] + rd();
    int S = (1 << k) - 1;
    for (int s = 0; s <= S; ++s) // 已经用了的硬币集合
        for (int k_ = 0; k_ < k; ++k_) { // 打算新加入的硬币是哪个
            if (!((1 << k_) & s)) {
                f[s | (1 << k_)] = max(f[s | (1 << k_)], find(f[s] + 1, n, w[k_]));
            }
        }
    int ans = -1;
    for (int s = 0; s <= S; ++s)
        if (f[s] == n) ans = max(ans, solve(s, k));
    printf("%d\n", ans);
    return 0;
}

总结

状压DP是一个优化爆搜的方式，爆搜我们有好多好多状态，状压DP可以把状态压到一起，然后一起转移，这就起到了优化的效果。

可以观察到的是，用状压解决的问题，被压的状态因为是指数级别的，所以不会很大，一般只有十几。

继续做题

洛谷P2704

给一网格图，网格图上有些位置可以放士兵，有些不可以，一个士兵的攻击范围是上下左右各两格，要求摆放士兵的时候不能在别人的攻击范围里，问最多能放多少个士兵。

思路：采取前面做题的思路，把一行的状态压起来，行内冲突提前预处理。不一样的是，这次不仅需要知道上一行的状态，需要知道上上行的状态，才能决定当前行能怎么放，所以定义状态为 f[i][s1][s2] 表示，当前处理到了第 行，第 行的状态时 ，再上一行的状态时 ，这样子我们就能DP啦！需要注意的是，在更新答案的时候，如果我们在循环里去数这一行和上一行比，增加了多少 的位置会 T， 所以在预处理的时候就把每个合法的状态里士兵的个数记下来。还有就是，这个DP数组，如果按之前的想法开需要 ，开不下了捏，所以我们需要对合法的 s 进行重编号，那要开多大呢？就是提前打个表数一下。还有这个判断一行的状态是否合法的时候，可以稍微优化一下。

打表如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
inline bool valid (int x) {
    if (x & (x >> 1)) return 0;
    if (x & (x >> 2)) return 0;
    return 1;
}

int main() {
 	int cnt = 0;
    int S = (1 << 10) - 1;
    for (int s = 0; s <= S; ++s)
        if (valid(s)) cnt++;
	printf("%d\n", cnt);
}

打表结果是60。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#define N 107

vector<int> V;
int mp[N], f[N][67][67], c[67];

inline bool valid (int x) {
    if (x & (x >> 1)) return 0;
    if (x & (x >> 2)) return 0;
    return 1;
}

inline int count (int s) {
    int cnt = 0;
    while (s) {
        if (s & 1) cnt++;
        s >>= 1;
    }
    return cnt;
}

int main() {
    int n = rd(), m = rd();
    for (int i = 1; i <= n; ++i)
        for (int j = 0; j < m; ++j) {
            char c = getchar();
            for (; c != 'H' && c != 'P'; c = getchar()) ;
            mp[i] = ((mp[i] << 1) | (c == 'P'));
        }
    int S = (1 << m) - 1;
    for (int s = 0; s <= S; ++s)
        if (valid(s)) {
            V.push_back(s);
            c[V.size() - 1] = count(s);
        }
    int tot = V.size();
    for (int i = 1; i <= n; ++i) // 枚举行数
        for (int i1 = 0; i1 < tot; ++i1) { // 枚举当前行的状态
            int s1 = V[i1];
            if ((s1 & mp[i]) != s1) continue;
            for (int i2 = 0; i2 < tot; ++i2) { // 枚举上一行的状态
                int s2 = V[i2];
                if (i > 1 && (s2 & mp[i - 1]) != s2) continue;
                if ((s1 & s2)) continue;
                for (int i3 = 0; i3 < tot; ++i3) { // 枚举上上行的状态
                    int s3 = V[i3];
                    if (i > 2 && (s3 & mp[i - 2]) != s3) continue;
                    if ((s1 & s3) > 0 || (s2 & s3) > 0) continue;
                    f[i][i1][i2] = max(f[i][i1][i2], f[i - 1][i2][i3] + c[i1]);
                }
            }
        }
    int ans = 0;
    for (int i1 = 0; i1 < tot; ++i1)
        for (int i2 = 0; i2 < tot; ++i2)
            ans = max(ans, f[n][i1][i2]);
    printf("%d\n", ans);
    return 0;
}

2021女生赛C连锁超市

有 个景点，每个景点隶属于一个公司，一个公司有一个红包金额，走到一个景点就可以领取该公司的红包，但一个公司的红包只能领一次。景点之间通过缆车连接，且只会网海拔高的地方走。

思路：看到这个数据范围，感觉压谁都不对……首先，我们来判断我们需要哪些条件来进行转移，首先我要知道哪些公司的红包我已经领过了，其次我还得知道，我现在在哪个景点，这将决定我接下来能往哪里走。知道自己需要什么以后，其实还是挺清晰的，刚开始我还在想要把景点压一起，但确实，其实我并不关心我走过哪些点，因为我只会沿着这个缆车往上走，我肯定不会经过重复的点。所以我们要压的是公司，问题是公司的数量跟景点的数量是一样的……呜呜呜，这我咋压。理性分析以后，我们可以发现，其实我们并不关心所有的公司，如果一个公司只有一个景点，那我想也不用想，走到就拿，不需要关心之前有没有走到过，因为必不可能，这样子想想，最差情况下，被压的公司数，就是点数的一半，啊！我能压了！对于初态，因为强制从 号点开始，分两种情况讨论：1.该点的公司只有一个景点 2.该点的公司不只有一个景点，就这样，初态也解决啦！

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
int f[1 << 18][36], cnt[36], c[36], w[36], ans[36], id[36];
bool vis[36];
vector<int> V[36];
 
int main() {
    int n = rd(), m = rd();
    for (int i = 0; i < n; ++i) ++cnt[c[i] = rd() - 1];
    for (int i = 0; i < n; ++i) w[i] = rd();
    for (int i = 0; i < m; ++i) {
        int u = rd(), v = rd();
        V[u - 1].push_back(v - 1);
    }
    int n_ = 0;
    for (int i = 0; i < n; ++i)
        if (!vis[c[i]] && cnt[c[i]] > 1) {
            id[c[i]] = n_++;
            vis[c[i]] = 1;
        }
    if (vis[c[0]]) f[1 << id[c[0]]][0] = w[c[0]];
    else f[0][0] = w[c[0]];
    int S = (1 << n_) - 1;
    for (int s = 0; s <= S; ++s)
        for (int u = 0; u < n; ++u) {
            ans[u] = max(ans[u], f[s][u]);
            for (auto v : V[u]) {
                if (cnt[c[v]] > 1 && !(s & (1 << id[c[v]]))) f[s | (1 << id[c[v]])][v] = max(f[s | (1 << id[c[v]])][v], f[s][u] + w[c[v]]);
                else if (cnt[c[v]] == 1) f[s][v] = max(f[s][v], f[s][u] + w[c[v]]);
                else f[s][v] = max(f[s][v], f[s][u]);
            }
        }
    for (int i = 0; i < n; ++i) printf("%d\n", ans[i]);
    return 0;
}

arc058E

问一个长度为 的数字序列，数字的范围是 0~10 。有多少种满足：有一段区间，把它拆成三段后，三段的区间和从前往后依次为 。答案对 取模。

思路：这题看起来跟状压也没啥关系……被Co老师喂了奇妙做法。其实这个问题可以转换成，问一个序列里，是否存在一个位置，满足以它结尾的后缀和里，包含 。所以我们就记状态集为从 0 ~ x + y + z 是否在以 为结尾的后缀和里。（呜呜，中文好难，不知道自己在写啥……）。如果一个位置满足了这个条件，那它后面的数字就可以随便放了，也就是 ，其中 len 表示，后面的长度，所以我们需要预处理出来 10 的各个幂次。写到这里，再来明确一下状态，状态 f[i][s] 表示，当前处理到序列中第 个数，且以该数结尾的后缀和中出现了的在 0 ~ x + y + z 的数字的集合为 s 。目标状态是啥呢？就是包含 z, y + z, x + y + z 即代码里的 tar 。下一个头疼的就是，长度 +1 的时候，我的集合 s 要怎么变，首先之前所有的后缀和都要加上这个新加的数，并且新增了一个后缀和就是这个新加的数，需要注意的是，可能会有状态溢出 x + y + z ，一旦溢出了，我们在枚举状态的时候就枚举不到了，所以需要和全局最大的 S 与一下。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#define mod 1000000007
#define ll long long
 
int f[47][1 << 18], pw10[47];
 
int main() {
    int n = rd(), x = rd(), y = rd(), z = rd();
    ll ans = 0;
    pw10[0] = 1;
    for (int i = 1; i <= n; ++i) pw10[i] = 1ll * pw10[i - 1] * 10 % mod;
    int S = (1 << (x + y + z + 1)) - 1;
    int tar = (1 << (x + y + z)) | (1 << (y + z)) | (1 << z);
    f[0][0] = 1;
    for (int i = 0; i <= n; ++i)
        for (int s = 0; s <= S; ++s) {
            if ((s & tar) == tar) ans = (ans + 1ll * f[i][s] * pw10[n - i]) % mod;
            else {
                for (int j = 1; j <= 10; ++j) {
                    int s_ = (((s << j) | (1 << j)) & S);
                    f[i + 1][s_] = (f[i + 1][s_] + f[i][s]) % mod;
                }
            }
        }
    printf("%lld\n", ans);
    return 0;
}
  • Post title：bitmask 状压DP
  • Post author：Eva.Q
  • Create time：2022-06-29 14:34:05
  • Post link：https://qyy/2022/06/29/Algorithm/bitmask/
  • Copyright Notice：All articles in this blog are licensed under BY-NC-SA unless stating additionally.