状压 DP 稍微进阶

· · 算法·理论

当 \texttt{dp} 状态数很多,甚至与 n 挂钩,但是每个状态却很小,可以使用状压 DP,将状态压缩成一个 2 进制数或 3 进制数。

显然,状压 DP 只能应用在 n 很小的时候。

当然,你也可以状压别的方向。

通常有以下三种状压:

棋盘状压 / 集合状压的状压方法:

S = \sum_{i = 0}^{n - 1} 2^i a_{i + 1}

一些常用二进制操作:

棋盘状压

P1896

预处理出一个 num 和 cnt 数组,num_i 表示第 i 个使得一行没有国王互相攻击的行状态,cnt_S 表示 S 中 1 的数量,可以使用 (i & (i >> 1)) == 0 判断一行的国王之间能否互相攻击。

设 dp_{i, j, S} 表示前 i 行,放了 j 个国王,本行的状态为 S 的合法方案数。

显然,枚举当前行状态和上一行状态可以直接枚举 num。

设枚举的上一行状态为 S2,如果 (S & S2) == 0 && (S & (S2 << 1)) == 0 && S & (S2 >> 1) == 0,则 S, S2 是合法,枚举 j,如果 j - cnt_{S}\ge 0,则:

dp_{i, j, S} = dp_{i, j, S} + dp_{i - 1, j - cnt_{S2}, S2}

答案就是 \sum_i dp_{n, k, num_i}。

for (int i = 0; i <= qwq; i++) {
    int cntt = 0, ti = i;
    while (ti) {
        if (ti & 1) cntt++;
        ti >>= 1;
    }
    cnt[i] = cntt;
    if ((i & (i >> 1)) == 0) num[++t0t] = i;
}
dp[0][0][0] = 1;
for (int i = 1; i <= n; i++)
    for (int j = 1; j <= t0t; j++)
        for (int k = 1; k <= t0t; k++)
            if ((num[j] & num[k]) == 0 && (num[j] & (num[k] << 1)) == 0 && (num[j] & (num[k] >> 1)) == 0)
                for (int l = 0; l <= K; l++)
                    if (l - cnt[num[j]] >= 0) dp[i][l][num[j]] += dp[i - 1][l - cnt[num[j]]][num[k]];
for (int i = 1; i <= t0t; i++) ans += dp[n][K][num[i]];

P2704

棋盘状压板子。

逐行状压,dp_{i, S, T} 表示到第 i 行,当前行和上一行状态为 S, T 的最大摆放数。

转移枚举上上行即可,判断很简单,转移就是:

dp_{i, s, t} = \max(dp_{i, s, t}, dp_{i - 1, t, k} + \text{popcount}(s))
for (int i = 0; i <= qwq; i++) {
    if ((a[1] & i) || (i & (i >> 2)) || (i & (i >> 1))) continue;
    dp[1][i][0] = cnt[i];
}
for (int i = 2; i <= n; i++) {
    for (int S = 0; S <= qwq; S++) {
        if ((i > 2 && (a[i - 2] & S)) || (S & (S >> 2)) || (S & (S >> 1))) continue;
        for (int t = 0; t <= qwq; t++) {
            if ((a[i - 1] & t) || (t & (t >> 2)) || (t & (t >> 1))) continue;
            if (S & t) continue;
            for (int s = 0; s <= qwq; s++) {
                if ((a[i] & s) || (s & (s >> 2)) || (s & (s >> 1))) continue;
                if ((s & S) || (s & t)) continue;
                dp[i][s][t] = max(dp[i][s][t], dp[i - 1][t][S] + cnt[s]);
            }
        }
    }
}

P10975

考虑逐行状压 DP。

因为我们只需要考虑上一行对这一行的影响,所以我们把纵向可以和上一行形成一个小矩阵的设为 1,其他都是 0。

那么,两行之间合法的条件肯定是交集为 0,一行内合法的条件为连续 0 的个数为偶数个。

设 dp_{i, S} 表示第 i 行状态为 S,转移为:

dp_{i, j} \to dp_{i, j} + dp_{i - 1, k}
bool check(int x) {
    bool cnt= 0, qwq = 0;
    for (int j = 0; j < m; j++) {
        if ((x >> j) & 1) {
            qwq |= cnt;
            cnt = 0;
        } else cnt ^= 1;
    }
    return ((qwq | cnt) == 0);
}
dp[0][0] = 1;
for (int i = 0; i < (1 << m); i++) flg[i] = check(i);
for (int i = 1 ;i <= n; i++)
    for (int j = 0; j < (1 << m); j++)
        for (int k = 0; k < (1 << m); k++)
            if ((j & k) == 0 && flg[j | k]) dp[i][k] += dp[i - 1][j];

集合状压

P5911

状压 DP 模板。

令 dp_S 表示选了 S 的人过河,转移先预处理出一个集合的重量和价值,枚举子集一下即可。

for (int S = 1; S <= qwq; S++) 
    for (int T = S; T; T = (T - 1) & S)
        if (awa[T] <= W) dp[S] = min(dp[S], dp[S ^ T] + cost[T]);

P6883

考虑状压 DP。

令 dp_{S} 状态 S 的杯子中有水的最小代价。

求答案:

\text{ans} = \min_{S} [\text{popcount}(S)\le K] dp_{S}

你发现从 i 倒水到 j,然后从 j 倒水到 k 可能比直接由 i 倒水到 k 更优,所以先跑一遍 floyd。

对于转移:

dp_S = \min_{i\not\in S}\min_{j\in S} dp_{S | i} + dist(i, j)
for (int S = qwq - 1; ~S; S--) {
    for (int i = 1; i <= n; i++) {
        if (S & (1 << i - 1)) continue;
        for (int j = 1; j <= n; j++) {
            if (!(S & (1 << j - 1))) continue;
            dp[S] = min(dp[S], dp[S | (1 << i - 1)] + dist[i][j]);
        }
    }
}

P4877

考虑状压 DP。

奖励首先按 K_i 为第一关键字排序,P_i 为第二关键字排序。

令 dp_{i, S} 表示前 i 个比赛,选了状态 S:

dp_{i, S} = \max_{j\in S} dp_{i - 1, S\oplus j} + S_{i, j}

然后对于奖励:

dp_{i, S} = dp_{i, S} + \sum_{j = 1}^n [K_j = i][dp_{i, S}\ge P_j] A_j
for (int t = 0; t < qwq; t++) {
    int cnt = popcount(t);
    for (int i = 1; i <= n; i++)
        if ((t >> (i - 1)) & 1) dp[t] = max(dp[t], dp[t ^ (1 << (i - 1))] + s[i][cnt]);
    for (int i = 1; i <= b; i++)
        if (cnt == a[i].k && dp[t] >= a[i].p) dp[t] += a[i].a;
}

P10561

令 dp_S 表示位置集合为 S,且从大到小插入的最小代价。

那么此时插入的数为 [k - |S|, k]。

考虑插入 k - |S| 到位置 p 的代价:

于是对于当前状态求出每个点往左往右连续 0 段长度。

那么设连续 0 段左右端点位 [x, y],则对于左端点在 [x, p] 且右端点在 [p, y] 的区间都会贡献。

对于这种区间的数量可以直接暴力预处理。

for (int S = 0; S < (1 << n); S++) {
    if (popcount(S) >= k) continue;
    for (int i = 1; i <= n; i++) {
        if ((S >> (i - 1)) & 1) L[i] = 0;
        else L[i] = L[i - 1] + 1;
    }
    for (int i = n; i >= 1; i--) {
        if ((S >> (i - 1)) & 1) R[i] = 0;
        else R[i] = R[i + 1] + 1; 
    }
    for (int p = 1; p <= n; p++) {
        if ((S >> (p - 1)) & 1) continue;
        dp[S | (1 << p - 1)] = min(dp[S | (1 << p - 1)], dp[S] + sum[p][p - L[p] + 1][p + R[p] - 1] * (k - popcount(S)));
    }
}

P10339

考虑求出最短路图,然后一遍 \texttt{topu} 求出每个点 u 的 mask_u 表示 u 在那些受灾点的最短路上。

转移:

dp_{S|mask_i} = \min(dp_{S|mask_i}, dp_S + 1)
dij();
build();
for (int i = 1; i <= n; i++)
    if (sz[i]) dpp[i] = 1 << (ys[i] - 1);
queue <int> q;
for (int i = 1; i <= n; i++)
    if (!in[i]) q.push(i);
while (!q.empty()) {
    int u = q.front();
    q.pop();
    for (auto x : g[u]) {
        int v = x.v;
        dpp[v] |= dpp[u];
        if (!(--in[v])) q.push(v);
    }
}
memset(dp, 0x3f, sizeof(dp));
dp[0] = 0;
for (int S = 1; S < (1 << k); S++)
    for (int i = 1; i <= n; i++)
        if (buji[i] && (S & ~dpp[i]) != S) dp[S] = min(dp[S], dp[S & ~dpp[i]] + 1);
cout << dp[(1 << k) - 1];

P2473

状压,令 dp_{i, S} 表示第 i 次状态为 S 采取最优策略获得分值的期望。

期望题考虑倒推。

我们枚举掉下来的宝物 k:

for (int i = K; i >= 1; i--) {
    for (int j = 0; j < (1 << n); j++) {
        for (int k = 1; k <= n; k++) {
            if ((j & s[k]) == s[k]) dp[i][j] += max(dp[i + 1][j], dp[i + 1][j | (1 << (k - 1))] + p[k]) * 1.0 / n;
            else dp[i][j] += dp[i + 1][j] * 1.0 / n;
        }
    } 
} 

P2396

令 dp_S 表示选择状态 S 的卡片的方案数,f_S 表示状态 S 的卡片可以到达的位置。

若 f_S 为厄运数字显然无法转移。

$$ f_S = f_{S\setminus \text{lowbit}(S)} + f_{\text{lowbit}(S)} $$ $dp$ 的转移也是简单的,由去掉一个 $1$ 的位置转移即可: $$ dp_S = \sum_{i\in S} dp_{S\setminus i} $$ ```cpp for (int i = 1; i < 1 << n; i++) { f[i] = f[i ^ lowbit(i)] + f[lowbit(i)]; if (f[i] == a[1] || f[i] == a[2]) continue; for (int now = i; now; now ^= lowbit(now)) dp[i] = (dp[i] + dp[i ^ lowbit(now)]) % mod; } ``` ### [P3694](https://www.luogu.com.cn/problem/P3694) $dp_S$ 表示排好了状态为 $S$ 的乐队的最小出列数量。 $len_S$ 表示排好状态为 $S$ 的乐队需要的位置: $$ len_S = \sum_{i\in S} cnt_i $$ 其中 $cnt_i$ 是乐队 $i$ 的人数。 $s_{i, j}$ 表示前 $i$ 个人里有多少属于 $j$ 乐队,前缀和容易预处理。 那么转移考虑新加入的乐队 $k$,则乐队 $k$ 占用的区间为: $$ [l = len_{S\setminus k}, r = len_S] $$ 则这个乐队 $k$ 中不属于这个区间的都需要移动,转移方程为: $$ dp_{S} = \min(dp_S, dp_{S\setminus k} + cnt_k - (s_{r, k} - s_{l - 1, k})) $$ ```cpp for (int i = 1; i <= n; i++) { cin >> a[i]; for (int j = 1; j <= m; j++) s[i][j] = s[i - 1][j]; s[i][a[i]]++; cnt[a[i]]++; } memset(dp, 0x3f, sizeof(dp)); dp[0] = 0; for (int mask = 0; mask < (1 << m); mask++) { for (int j = 1; j <= m; j++) if ((mask >> j - 1) & 1) len[mask] += cnt[j]; for (int j = 1; j <= m; j++) { if ((mask >> j - 1) & 1) { int T = mask ^ (1 << j - 1); int l = len[T] + 1, r = len[mask]; dp[mask] = min(dp[mask], dp[T] + cnt[j] - (s[r][j] - s[l - 1][j])); } } } ``` ### [P11856](https://www.luogu.com.cn/problem/P11856) $dp_{i, j}$ 表示前 $i$ 个数,状态为 $j$ 的不合法方案数。 $j$ 的状态如下: 例如后缀和为 $10, 9, 5, 1$,则 $j = 11000010001

转移枚举新加入的数 d,则新的状态 to = (j << d | (1 << (d - 1))) & (qwq - 1),其中 qwq 是状态上限,& (qwq - 1) 相当于使 to 不超过上限,j << d 因为末尾加了 d,后缀和都增加了,左移 d 位,| (1 << (d - 1)) 相当于使 d 对应的位变为 1。

通过判断后缀是否含有 x, x + y, x + y + z 来判断是否合法,即 (to >> (x - 1) & 1) && (to >> (x + y - 1) & 1) && (to >> (x + y + z - 1) & 1),合法摄取。

显然,dp_{i + 1, to} = dp_{i + 1, to} + dp_{i, j}。

总方案数显然为 10^n,答案为 10^n - \sum_i dp_{n, i}。

int qwq = (1 << (x + y + z));
dp[0][0] = 1;
for (int i = 0; i < n; i++) {
    for (int j = 0; j < qwq; j++) {
        for (int d = 1; d <= 10; d++) {
            int to = (j << d | (1 << (d - 1))) & (qwq - 1);
            if ((to >> (x - 1) & 1) && (to >> (x + y - 1) & 1) && (to >> (x + y + z - 1) & 1)) continue;
            dp[i + 1][to] = (dp[i + 1][to] + dp[i][j]) % mod;   
        }
    }
}
ans = qpow(10, n);
for (int i = 0; i < qwq; i++) ans = (ans - dp[n][i] + mod) % mod;

P3959

我们发现,最后藏宝室一定构成一棵树,初始选的点为根。

设 dp_{i, S} 表示扩展到第 i 层状态为 S 的最小代价。

对于转移,我们考虑枚举 S 的子集 T,由 dp_{i - 1, T} 转移:

dp_{i, S} = \min(dp_{i, S}, dp_{i - 1, T} + cost(T, S)\times i)

其中 cost(S, T) 表示状态 S 转移到 T 的最小代价(也就是挖出 S\setminus T),其中 S 是 T 的子集。

考虑 cost 怎么计算。

我们对于 S 到 T 每个新增的点,找出其在 T 中最近的相邻的点累加到 cost,因为对于第 i 层的点父亲一定是第 i - 1 层的点,边选最短显然最优。

然后就做完了。

for (int s = 0; s < N; s++) {
    for (int t = s; t; t = (t - 1) & s) {
        if (t == s) continue;
        int x = s ^ t;
        for (int i = 1; i <= n; i++) {
            if (!(x & (1 << i - 1))) continue;
            int Min = INT_MAX;
            for (int j = 1; j <= n; j++) {
                if (!(t & (1 << j - 1))) continue;
                Min = min(Min, dist[i][j]);
            }
            cost[t][s] += Min;
        }
    }
}
dp[0][0] = 0;
for (int i = 0; i <= n; i++) dp[0][1 << i] = 0;
for (int i = 1; i <= n; i++) {
    for (int s = 0; s < N; s++) {
        for (int t = s; t; t = (t - 1) & s) {
            if (t == s) continue;
            dp[i][s] = min(dp[i][s], dp[i - 1][t] + cost[t][s] * i);
        }
    }
}

P7519

若直接状压 DP,需要记录上一个队伍,上一个队伍的 b_i,当前 b_i 的总和,显然会炸。

我们发现,对于每个限制,对应一个排名,最多贡献 1,于是我们考虑对于一个顺序考虑最优的 b_i 分配。

我们显然需要相邻增量最小,考虑若需要 b_i\le b_j 的增量:

我们令 \Delta(i, j) 为上面这个东西。

我们发现,若第 s 步加上了差分代价 \Delta(p_{s - 1}, p_s),这个代价会一直计算 n - s + 1 次。

考虑费用提前计算,也就是每次将当前的贡献直接加入到 DP 中。

我们发现,这样我们只需要枚举上一个队伍即可,不需要记录 b_i,复杂度就对了。

设 dp_{S, i, j} 表示状态为 S,当前队伍为 i,通过了 j 道题,那么:

dp_{S, i, j}\to dp_{S, i, j} + dp_{S\setminus i, k, j - mul\times \Delta(k, i)}

根据我们前面的推论,mul = n - |S| + 1。

最后注意我们需要预处理若这个数是第一个的代价。

for (int i = 1; i <= n; i++)
    for (int j = 1; j <= n; j++) diff[i][j] = max(0ll, a[i] - a[j] + (i < j));
for (int i = 1; i <= n; i++) fir[i] = a[id] - a[i] + (i > id);
dp[0][0][0] = 1;
for (int mask = 1; mask < (1 << n); mask++) {
    int cnt = popcount(mask);
    if (cnt == 1) {
        for (int i = 1; i <= n; i++)
            if (mask & (1 << i - 1) && n * fir[i] <= m) dp[mask][i][n * fir[i]] = 1;
        continue;
    }
    for (int i = 1; i <= n; i++) {
        if (!mask & (1 << i - 1)) continue;
        int T = mask ^ (1 << i - 1);
        int qwq = n - popcount(mask) + 1;
        for (int j = 1; j <= n; j++) {
            if (!T & (1 << j - 1)) continue;
            for (int k = qwq * diff[j][i]; k <= m; k++) dp[mask][i][k] += dp[T][j][k - qwq * diff[j][i]];
        }
    }
}