状压 DP 稍微进阶
kaikai_qwq · · 算法·理论
当
显然,状压 DP 只能应用在
当然,你也可以状压别的方向。
通常有以下三种状压:
- 棋盘上状压,这类问题通常在一个棋盘上进行。我们将一行的状态压缩成一个二进制数,然后逐行进行转移,确保当前行的状态不与上一行冲突。
- 集合上状压,这类问题的状态直接对应一个集合,二进制位上的
01 代表某个元素是否被选中,通常用于解决需要枚举元素子集的问题。 - 基于连通性的状压,这是轮廓线 DP / 插头 DP,太困难了,就不细说了。
棋盘状压 / 集合状压的状压方法:
- 因为状态数过多,你不能用
x 个数来表示状态,可以使用一个二进制 / 三进制数来表示,即dp_{i_1, i_2, \dots, i_x}\to dp_{(i_1i_2\dots i_x)} 。 - 设当前行列 / 集合的状态为
a_1, a_2, \dots, a_n ,其中a_i 为0 或1 ,我们状压成这样一个状态:
- 此时,
S 的第i 位就对应着a_{i + 1} 。
一些常用二进制操作:
(mask >> i) & 1:检查第i 位是否为1 。mask | (1 << i):将第i 位设为1 。mask & (~(1 << i)):将第i 位设为0 。mask & (-mask):获取最低位的1 的位置。mask & (mask - 1):将最低位的1 置为0 (用于枚举子集)。mask ^ (1 << i):若第i 位为1 则变为0 。for (int sub = mask; sub; sub = (sub - 1) & mask):枚举mask 的所有子集,复杂度O(3^n) 。
棋盘状压
P1896
预处理出一个 (i & (i >> 1)) == 0 判断一行的国王之间能否互相攻击。
设
显然,枚举当前行状态和上一行状态可以直接枚举
设枚举的上一行状态为 (S & S2) == 0 && (S & (S2 << 1)) == 0 && S & (S2 >> 1) == 0,则
答案就是
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
棋盘状压板子。
逐行状压,
转移枚举上上行即可,判断很简单,转移就是:
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。
因为我们只需要考虑上一行对这一行的影响,所以我们把纵向可以和上一行形成一个小矩阵的设为
那么,两行之间合法的条件肯定是交集为
设
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 模板。
令
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。
令
求答案:
你发现从
对于转移:
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。
奖励首先按
令
然后对于奖励:
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
令
那么此时插入的数为
考虑插入
- 所有包含
p 但不包含其他数的区间,就会贡献k - |S| 。
于是对于当前状态求出每个点往左往右连续
那么设连续
对于这种区间的数量可以直接暴力预处理。
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
考虑求出最短路图,然后一遍
转移:
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
状压,令
期望题考虑倒推。
我们枚举掉下来的宝物
- 若能吃,也就是
S & mask[k] == k:dp_{i, j}\to dp_{i, j} + \max(dp_{i + 1, j}, dp_{i + 1, j\cup k} + p_k)\div n 。 - 若不能吃:
dp_{i, j}\to dp_{i, j} + dp_{i + 1, j}\div n 。
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
令
若
转移枚举新加入的数 to = (j << d | (1 << (d - 1))) & (qwq - 1),其中 & (qwq - 1) 相当于使 j << d 因为末尾加了 | (1 << (d - 1)) 相当于使
通过判断后缀是否含有 (to >> (x - 1) & 1) && (to >> (x + y - 1) & 1) && (to >> (x + y + z - 1) & 1),合法摄取。
显然,
总方案数显然为
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
我们发现,最后藏宝室一定构成一棵树,初始选的点为根。
设
对于转移,我们考虑枚举
其中
考虑
我们对于
然后就做完了。
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,需要记录上一个队伍,上一个队伍的
我们发现,对于每个限制,对应一个排名,最多贡献
我们显然需要相邻增量最小,考虑若需要
- 若
j < i 则增量为a_i - a_j 。 - 否则增量为
a_i - a_j + 1 。
我们令
我们发现,若第
考虑费用提前计算,也就是每次将当前的贡献直接加入到 DP 中。
我们发现,这样我们只需要枚举上一个队伍即可,不需要记录
设
根据我们前面的推论,
最后注意我们需要预处理若这个数是第一个的代价。
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]];
}
}
}