浅谈状压 DP

· · 算法·理论

前言(废话)

本人为区一,写的有问题还望多多包涵。

正题

常用位运算

(S >> i) & 1:检查第 i 位是否为 1。

S | (1 << i):将第 i 位设为 1。

S & (~(1 << i)):将第 i 位变为 0。

S & (-S):获取最低位的 1 的位置。

S & (S - 1):将最低位的 1 变为 0(用于枚举子集)。

S ^ (1 << i):将 S 的第 i 位取反。

for (int T = S; T; T = (T - 1) & S):枚举 S 的所有子集,总复杂度 O(|S|^3)。

例题

普通状压

状压 DP 常熟极小,所以这 2 种可以过。

首先本质不同的罚款只有 n^2 种。

发现可以从大到小插入,假入在第 i 位插入,[l,i) 和 (i,r] 都没被插入,则只有左端点在 [l,i],右端点在 [i,r] 的区间贡献和 i 有关。

然后插入时可以向左右扩展找到 l 和 r,如果同时统计贡献的话复杂度较高,O(n^5) 预处理插入的贡献即可。

#include<bits/stdc++.h>
#define int long long

using namespace std;

const int N = 2e1 + 10;
const int M = (1 << 20);
int n, k, m, cr[N], a[N][N], b[N][N][N], dp[M];
// b[i][l][r]:在 i 插入,[l,i) 和 (i,r] 没被插入的贡献

signed main(void) {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    cin >> n >> k >> m;
    for(int i = 1; i <= m; i++) {
        int l, r;
        cin >> l >> r;
        a[l][r]++;
    } 
    for(int i = 1; i <= n; i++) {
        cr[i] = k - i + 1;
        if(i > k) cr[i] = 0;
    }
    for(int i = 1; i <= n; i++) 
        for(int l = 1; l <= i; l++) 
            for(int r = i; r <= n; r++) 
                for(int ll = l; ll <= i; ll++) 
                    for(int rr = i; rr <= r; rr++) 
                        b[i][l][r] += a[ll][rr]; 
    memset(dp, 0x3f, sizeof dp), dp[0] = 0;
    for(int S = 1; S < (1 << n); S++) {
        int cnt = 0, ss = S;
        while(ss) cnt += (ss & 1), ss >>= 1;
        for(int i = 1; i <= n; i++) {
            if(!(S & (1 << i - 1))) continue;
            int T = S ^ (1 << i - 1), l = i, r = i;
            while(l > 1 && !(S & (1 << l - 2))) l--;
            while(r < n && !(S & (1 << r - 0))) r++;
            dp[S] = min(dp[S], dp[T] + b[i][l][r] * cr[cnt]);
        }
    } cout << dp[(1 << n) - 1];
}

P7296 [USACO21JAN] Uddered but not Herd G

思路和上一题有异曲同工之处。

设 dp_S 表示将 S 插入到字母表的前 |S| 位的最小轮数。

考虑转移,将 i 插入到字母表的 |S| + 1 位,我们发现若一个 S 中的元素出现在 i 的左边,此时又唱了一轮字母表。

然后预处理相邻字母为 s_1 和 s_2 的数量 sum_{s_1,s_2},O(2^nn^2) DP 即可。

这题因为不包含 Mildred 中的字母,只有 20 种字符,需要离散化。

#include<bits/stdc++.h>
#define int long long

using namespace std;

const int N = 1e5 + 10;
const int M = (1 << 20);
int n, cnt, lsh[N], a[N];
int dp[M], sum[30][30];
string s;

signed main(void) {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    cin >> s; 
    n = s.size(); 
    s = ' ' + s;
    for(int i = 1; i <= n; i++) lsh[i] = s[i];
    sort(lsh + 1, lsh + 1 + n);
    cnt = unique(lsh + 1, lsh + 1 + n) - lsh - 1;
    for(int i = 1; i <= n; i++) a[i] = lower_bound(lsh + 1, lsh + 1 + cnt, s[i]) - lsh - 1;
    for(int i = 2; i <= n; i++) sum[a[i - 1]][a[i]]++;
    memset(dp, 0x3f, sizeof dp), dp[0] = 1;
    for(int S = 0; S < (1 << cnt); S++) {
        for(int i = 0; i < cnt; i++) {
            if((S & (1 << i))) continue;
            int T = S | (1 << i), val = dp[S];
            for(int j = 0; j < cnt; j++) {
                if((T & (1 << j))) {
                    val += sum[i][j];
                }
            } dp[T] = min(dp[T], val);
        }
    } cout << dp[(1 << cnt) - 1];
}

P7296 [USACO21JAN] Uddered but not Herd G

发现可以用 \text{Floyd} 得到最短路,再得到每个点再那些受灾区的最短路上。

然后发现这可以 DP,设 dp_S 表示 S 的受灾区最短路有补给点的最小代价。

暴力转移是 O(2^k\times n) 的,但是状压常熟极小,能过。

#include<bits/stdc++.h>
#define int long long

using namespace std;

const int N = 2e2 + 10;
const int M = (1 << 20);
int n, m, b, f[N], c[N];
int dis[N][N], sta[N], dp[M];


void Floyd() {
    for(int k = 1; k <= n; k++)
        for(int i = 1; i <= n; i++)
            for(int j = 1; j <= n; j++)
                dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
    for(int j = 1; j <= n; j++) {
        for(int i = 1; i <= m; i++) {
            if(dis[1][c[i]] == dis[1][j] + dis[j][c[i]])
                sta[j] |= (1 << i - 1);
        }
    }
}

signed main(void) {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    cin >> n >> b >> m;
    memset(dp, 0x3f, sizeof dp);
    memset(dis, 0x3f, sizeof dis);
    for(int i = 1; i <= n; i++) cin >> f[i];
    for(int i = 1; i <= m; i++) cin >> c[i];
    for(int i = 1; i <= n; i++) dis[i][i] = 0;
    for(int i = 1, u, v, w; i <= b; i++) {
        cin >> u >> v >> w;
        dis[u][v] = min(dis[u][v], w);
        dis[v][u] = min(dis[v][u], w);
    } Floyd(), dp[0] = 0;
    for(int S = 0; S < (1 << m); S++) {
        for(int i = 1; i <= n; i++) {
            if(!f[i]) continue;
            int T = S | sta[i];
            dp[T] = min(dp[T], dp[S] + 1);
        }
    } cout << dp[(1 << m) - 1];
}

P5911 [POI 2004] PRZ

直接设 dp_S 表示过桥状态为 S 的最小代价。

然后可以预处理不同集合的人一次性过桥的重量和时间。

枚举子集暴力转移即可,枚举子集复杂度总和是 O(3^n),能通过。

#include<bits/stdc++.h>
#define int long long

using namespace std;

const int N = 2e1 + 10;
const int M = (1 << 20);
int n, m, a[N], b[N], t[M], w[M], dp[M];

void getmin(int &x, int y) {x = min(x, y);}
void getmax(int &x, int y) {x = max(x, y);}

signed main(void) {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    cin >> m >> n;
    memset(dp, 0x3f, sizeof dp);
    for(int i = 1; i <= n; i++) cin >> a[i] >> b[i];
    for(int S = 1; S < (1 << n); S++) {
        for(int i = 1; i <= n; i++) {
            if(!(S & (1 << i - 1))) continue;
            getmax(t[S], a[i]), w[S] += b[i];
        }
    } dp[0] = 0;
    for(int S = 1; S < (1 << n); S++) {
        for(int T = S; T; T = (S & T - 1)) {
            if(w[T] <= m) getmin(dp[S], dp[S ^ T] + t[T]);
            if(T == 0) break;
        }
    } cout << dp[(1 << n) - 1];
}

P2704 [NOI2001] 炮兵阵地

对于这种棋盘上状压的经典题还是讲一下吧。

打一下表发现,在判断当前行是否合法后,每一行的状态只有 $O(n)$ 种。 直接设 $dp_{i,S,T}$ 表示考虑前 $i$行,第 $i$ 行为 $S$,第 $i - 1$ 行为 $T$。 枚举下一行转移,复杂度约为 $O(n^4)$。 ```cpp #include<bits/stdc++.h> #define int long long using namespace std; const int N = 1e2 + 10; const int M = (1 << 10); int n, m, sta[N], cnt[M]; int id[M], dp[N][N][N]; vector<int> v; void getmax(int &x, int y) {x = max(x, y);} signed main(void) { ios::sync_with_stdio(0); cin.tie(0), cout.tie(0); cin >> n >> m; for(int i = 1; i <= n; i++) for(int j = 1; j <= m; j++) { char ch; cin >> ch; if(ch == 'P') continue; sta[i] |= (1 << j - 1); } for(int S = 0; S < (1 << m); S++) { cnt[S] = __builtin_popcountll(S); int check = ((S << 2) | (S << 1) | (S >> 1) | (S >> 2)); if(!(check & S)) v.push_back(S), id[S] = v.size(); } memset(dp, -1, sizeof dp); dp[0][1][1] = 0; for(int i = 1; i <= n; i++) { for(int S : v) { if((S & sta[i])) continue; for(int T : v) { if((T & sta[i - 1])) continue; for(int A : v) { if(i > 1 && (A & sta[i - 2])) continue; if((S & T) | (S & A) | (T & A)) continue; if(dp[i - 1][id[T]][id[A]] < 0) continue; getmax(dp[i][id[S]][id[T]], dp[i - 1][id[T]][id[A]] + cnt[S]); } } } } int ans = 0; for(int S : v) for(int T : v) getmax(ans, dp[n][id[S]][id[T]]); cout << ans; } ``` #### [P7519 [省选联考 2021 A/B 卷] 滚榜](https://www.luogu.com.cn/problem/P7519) 设 $dp_{S,i,j,k}$ 表示考虑前 $i$ 个,前 $|S|$ 名为 $S$ 内元素,第 $|S|$ 名为 $i$,总过题数为 $j$,前一个过题数为 $k$。 发现枚举过题数太慢了 $O(m^2)$,发现可以贪心,每次尽量少选。 把 $b$ 差分一下,然后每次最小化当前的 $b$,因为是差分数组,所以会对后面带来贡献,额外计算对后面的贡献即可。 ```cpp #include<bits/stdc++.h> #define int long long using namespace std; const int N = 1e1 + 4; const int M = 5e2 + 10; int n, m, a[N], ma = 1; int dp[1 << N][N][M]; // [点集][当前位置][最小b总和] int lowbit(int x) {return x & -x;} signed main() { ios::sync_with_stdio(0); cin.tie(0), cout.tie(0); cin >> n >> m; int kk = (1 << n) - 1; for(int i = 1; i <= n; i++) cin >> a[i]; for(int i = 1; i <= n; i++) if(a[i] > a[ma]) ma = i; for(int i = 1; i <= n; i++) { int sum = n * (a[ma] - a[i]); if(ma < i) sum += n; if(sum > m) continue; dp[1 << i - 1][i][sum] = 1; } for(int S = 1; S <= kk; S++) { int cnt = n, S_ = S; while(S_) cnt -= S_ & 1, S_ >>= 1; for(int T = S; T; T -= lowbit(T)) { int j = __lg(lowbit(T)) + 1; for(int E = kk - S; E; E -= lowbit(E)) { // 用 lowbit 优化枚举元素 int i = __lg(lowbit(E)) + 1; for(int b = 0; b <= m; b++) { int sum = cnt * (a[j] - a[i]); if(j < i) sum += cnt; sum = max(sum, 0ll) + b; if(sum > m) continue; dp[S | (1 << i - 1)][i][sum] += dp[S][j][b]; } } } } int ans = 0; for(int i = 1; i <= n; i++) for(int j = 0; j <= m; j++) // 这里最小化了费用,所以 < m 也是合法的 ans += dp[kk][i][j]; cout << ans; } ``` #### [P3959 [NOIP 2017 提高组] 宝藏](https://www.luogu.com.cn/problem/P3959) 首先答案的图一定是个树。 考虑暴力枚举根节点(赞助的点),然后对树进行扩展。 发现扩展时的代价与新点的深度和边的长度有关,于是对其进行 DP。 设 $dp_{i,S}$ 表示考虑深度 $\le i$ 的点,已经选的点集为 $S$,最小的代价。 发现转移不方便,设辅助数组 $deta_{S,T}$ 表示将 $S$ 的点连边后变成 $T$ 的最小代价,然后就好转移了。 这里面会有错的转移,但它更不优,所以不用管。 ```cpp #include<bits/stdc++.h> #define int long long using namespace std; const int N = 1e1 + 3; const int M = (1 << 12); const int INF = 0x3f3f3f3f; int n, m, w[N][N], deta[M][M], dp[N][M]; void getmin(int &x, int y) {x = min(x, y);} int DP(int x) { memset(dp, 0x3f, sizeof dp); dp[0][1 << x - 1] = 0; for(int i = 1; i < n; i++) { for(int S = 1; S < (1 << n); S++) { for(int T = S; T; T = (T - 1) & S) { if(S == T) continue; getmin(dp[i][S], dp[i - 1][T] + deta[T][S] * i); } } } int res = INF; for(int i = 1; i < n; i++) getmin(res, dp[i][(1 << n) - 1]); return res; } signed main(void) { ios::sync_with_stdio(0); cin.tie(0), cout.tie(0); cin >> n >> m; memset(w, 0x3f, sizeof w); memset(dp, 0x3f, sizeof dp); for(int i = 1; i <= m; i++) { int u, v, c; cin >> u >> v >> c; getmin(w[u][v], c); getmin(w[v][u], c); } if(n == 1) {cout << 0; return 0;} for(int S = 1; S <= (1 << n); S++) { for(int T = S; T; T = (T - 1) & S) { if(T == S) continue; for(int i = 1; i <= n; i++) { int tmp = INF; if(!(((S ^ T) >> i - 1) & 1)) continue; for(int j = 1; j <= n; j++) if((T >> j - 1) & 1) getmin(tmp, w[j][i]); if(tmp == INF) {deta[T][S] = INF; break;} deta[T][S] += tmp; } } } // 预处理 deta int ans = INF; for(int i = 1; i <= n; i++) getmin(ans, DP(i)); cout << ans; } ``` #### [P2566 [SCOI2009] 围豆豆](https://www.luogu.com.cn/problem/P2566) 发现要判断豆豆是否被围住,这里用到射线定理: > 向任意方向引一条射线,如果射线与路径的交点为奇数个,那么豆豆能被围住,反之则不能。 然后在每一个起点跑一遍最短路,要加上豆豆被围住的状态这一维。 跑最短路时要更新豆豆,我们这里向右边引一条射线,所以在上下移动时更新贡献,左右移动不更新。 更新贡献还需要满足路径在豆豆右边,且只有向上移动到豆豆哪一行或向下离开哪一行才有贡献。 然后预处理一些贡献即可。 ```cpp #include<bits/stdc++.h> #define int long long using namespace std; const int N = 1e1 + 1; const int M = (1 << 9); const int fx[] = {0, 1, 0, -1, 0}; const int fy[] = {0, 0, 1, 0, -1}; int n, m, d, dd[N], dx[N], dy[N], v[M], ans; int q[N * N * M][3], h, w, vis[N][N][M], f[N][N][M]; char a[N][N]; void bfs(int sx, int sy) { memset(vis, 0, sizeof vis); memset(f, 0x3f, sizeof f); q[1][0] = sx, q[1][1] = sy; q[1][2] = 0, h = w = 1; vis[sx][sy][0] = 1; f[sx][sy][0] = 0; while(h <= w) { int nx = q[h][0]; int ny = q[h][1]; int ns = q[h][2]; for(int i = 1; i <= 4; i++) { int tx = nx + fx[i]; int ty = ny + fy[i]; int ts = ns; if(a[tx][ty] != '0') continue; if(i & 1) { for(int j = 1; j <= d; j++) { if(max(nx, tx) != dx[j]) continue; if(dy[j] < ty) ts ^= (1 << j - 1); } } // 更新豆豆贡献 if(vis[tx][ty][ts]) continue; f[tx][ty][ts] = f[nx][ny][ns] + 1; vis[tx][ty][ts] = 1; q[++w][2] = ts; q[w][0] = tx; q[w][1] = ty; } h++; } for(int S = 0; S < (1 << d); S++) ans = max(ans, v[S] - f[sx][sy][S]); } signed main(void) { ios::sync_with_stdio(0); cin.tie(0), cout.tie(0); cin >> n >> m >> d; for(int i = 1; i <= d; i++) cin >> dd[i]; for(int i = 1; i <= n; i++) for(int j = 1; j <= m; j++) { cin >> a[i][j]; int now = a[i][j] - '0'; if(now <= 0 || now > 9) continue; dx[now] = i, dy[now] = j; // 预处理豆豆信息 } for(int S = 0; S < (1 << d); S++) for(int i = 1; i <= d; i++) if((S >> i - 1) & 1) v[S] += dd[i]; for(int i = 1; i <= n; i++) for(int j = 1; j <= m; j++) if(a[i][j] == '0') bfs(i, j); cout << ans; } ``` ### 轮廓线 DP > 轮廓线用于维护已决策格子和未决策格子的分界线。 #### [P10975 Mondriaan's Dream / 蒙德里安的梦想](https://www.luogu.com.cn/problem/P10975) 轮廓线板子,维护放了一半的方块的插头,分类讨论一下即可。 ```cpp #include<bits/stdc++.h> #define int long long using namespace std; const int N = 1e1 + 2; int n, m, dp[2][1 << N], now; int get(int S, int x) {return (S >> x) & 1;} int clac(int x) {return (1 << x);} signed main(void) { ios::sync_with_stdio(0); cin.tie(0), cout.tie(0); while(cin >> n >> m) { if(n == 0) return 0; memset(dp, 0, sizeof dp); dp[now = 0][0] = 1; for(int i = 1; i <= n; i++) { now ^= 1; memset(dp[now], 0, sizeof dp[now]); for(int j = 0; j < (1 << m); j++) dp[now][j << 1] = dp[now ^ 1][j]; for(int j = 1; j <= m; j++) { now ^= 1; memset(dp[now], 0, sizeof dp[now]); for(int S = 0; S < (1 << m + 1); S++) { if(!dp[now ^ 1][S]) continue; int lc = get(S, j - 1); // 左插头 int uc = get(S, j); // 上插头 if(lc && uc) continue; // 方块不能是弯的。 if(!uc) dp[now][S ^ clac(j - 1)] += dp[now ^ 1][S]; if(!lc) dp[now][S ^ clac(j)] += dp[now ^ 1][S]; } } } cout << dp[now][0] << "\n"; } } ``` #### [P4363 [九省联考 2018] 一双木棋 chess](https://www.luogu.com.cn/problem/P3959) 轮廓线不止能维护例题那样的轮廓,例如这题维护的是放于没放的分界线。 根据依赖的传递性,发现 $(i,j)$ 能放必须满足其左上角的矩形只有 $(i,j)$ 是空的。 设 $0$ 为竖线,$1$ 为横线,发现固定有 $n$ 个 $0$,$m$ 个 $1$,且初始 $1$ 都在右边。 发现填充一个位置相当于让一个 $1$ 往左移动一位,于是会转移了。 发现不太好枚举状态,考虑直接用记搜。 ```cpp #include<bits/stdc++.h> #define int long long using namespace std; const int N = 1e1 + 5; const int M = (1 << 20); int n, m, a[N][N], b[N][N], dp[M]; void getmin(int &x, int y) {x = min(x, y);} void getmax(int &x, int y) {x = max(x, y);} int dfs(int sta, int now) { if(dp[sta] < 1e9) return dp[sta]; int res = -1e9 * (now * 2 - 1), x = n + 1, y = 1; for(int i = 0; i < n + m - 1; i++) { if((sta >> i) & 1) x--; else y++; if(((sta >> i) & 3) != 1) continue; if(now) getmax(res, dfs(sta ^ (3 << i), now ^ 1) + a[x][y]); else getmin(res, dfs(sta ^ (3 << i), now ^ 1) - b[x][y]); } return dp[sta] = res; } signed main(void) { ios::sync_with_stdio(0); cin.tie(0), cout.tie(0); cin >> n >> m; for(int i = 1; i <= n; i++) for(int j = 1; j <= m; j++) cin >> a[i][j]; for(int i = 1; i <= n; i++) for(int j = 1; j <= m; j++) cin >> b[i][j]; memset(dp, 0x3f, sizeof dp); dp[((1 << n) - 1) << m] = 0; cout << dfs((1 << n) - 1, 1); } ``` #### [P5056 【模板】插头 DP](https://www.luogu.com.cn/problem/P5056) 其实和普通的轮廓线没太大区别,评黑是因为要括号匹配和分讨。 分讨见代码,不过我代码极丑,轻喷。 ```cpp #include<bits/stdc++.h> #define int long long using namespace std; const int P = 299987; const int K = 3e5 + 10; const int N = 1e2 + 10; const int M = 1ll << 25; int n, m, a[N][N], ex, ey; int q[M][2], s[M][2], now; int p[N], cnt[2], ans; int h[K], Next[K]; char str[N]; void insert(int bit, int sum) { int u = bit % P + 1; for(int i = h[u]; i; i = Next[i]) { if(q[i][now] == bit) { s[i][now] += sum; return; } //去重 } Next[++cnt[now]] = h[u]; q[cnt[now]][now] = bit; s[cnt[now]][now] = sum; h[u] = cnt[now]; } // 可能转移到相同的状态,将方案数累加,用 hash 表的挂表法 signed main() { scanf("%lld %lld", &n, &m); for(int i = 1; i <= n; i++) { scanf("%s", str + 1); for(int j = 1; j <= m; j++) { if(str[j] == '*') continue; ex = i, ey = j; a[i][j] = 1; } } p[0] = 1; for(int i = 1; i <= 20; i++) p[i] = p[i - 1] << 2; cnt[0] = s[1][0] = 1; for(int i = 1; i <= n; i++) { for(int j = 1; j <= cnt[now]; j++) q[j][now] <<= 2; for(int j = 1; j <= m; j++) { memset(h, 0, sizeof h); int last = now; cnt[now ^= 1] = 0; for(int k = 1; k <= cnt[last]; k++) { int ct = q[k][last], sum = s[k][last]; int c1 = (ct >> (j - 1) * 2) & 3; int c2 = (ct >> j * 2) & 3; if(!a[i][j]) { // 不能放插头 if(!c1 && !c2) insert(ct, sum); }else if(!c1 && !c2) { // 没有插头 if(a[i + 1][j] && a[i][j + 1]) insert(ct + p[j - 1] + p[j] * 2, sum); // 新建 2 个新插头 } else if(!c1 || !c2) { // 只有一个插头 int tx = min(1ll, c1); int ty = min(1ll, c2); if(a[i + tx][j + ty]) insert(ct, sum); // 插头位置不变 if(a[i + ty][j + tx]) { // 插头位置改变 int ccb = c1 - c2; int tty = p[j] * ccb; int hkk = p[j - 1] * ccb; insert(ct - hkk + tty, sum); } } else if(c1 == c2) { // 都是左插头或右插头 // 此时要合并两个线路,将剩下的插头匹配 int ks = 1; int orz = ct - (p[j] + p[j - 1]) * c1; if(c1 == 1) { for(int b = j + 1; b <= m; b++) { int ccb = (ct >> b * 2) & 3; if(ccb) ks += 3 - ccb * 2; if(!ks) insert(orz - p[b], sum); if(!ks) break; } // 匹配右括号 } else { for(int b = j - 2; b >= 0; b--) { int ccb = (ct >> b * 2) & 3; if(ccb) ks += ccb * 2 - 3; if(!ks) insert(orz + p[b], sum); if(!ks) break; } // 匹配左括号 // 我这写法是不是有点诡异了( } } else if(c1 == 2 && c2 == 1) { // 刚好一左一右 // 两个插头匹配了 insert(ct - p[j - 1] * 2 - p[j], sum); } else if(i == ex && j == ey) ans += sum; // 到目标点了,统计答案 } } } printf("%lld", ans); } ```