34 · 状态压缩 DP 与数位 DP

前面几节的 DP 状态都是一个下标或一对下标。这一节的两种 DP 都换了“状态的形状”：状压把“用过哪些东西”压进一个 int 的二进制位；数位 DP把数字当成字符串，从高位往低位一位一位填。记忆化的套路完全一样，只是“状态长什么样”变了。

这一节的全部代码都建立在位运算上。三个工具先拆开：位运算本身、数 1 的个数、枚举子集。

#include <bits/stdc++.h>
using namespace std;

int main() {
    int S = 0b0101;                     // 集合 {0, 2}
    S |= 1 << 3;                        // 加入 3      → 0b1101
    S &= ~(1 << 0);                     // 移出 0      → 0b1100
    printf("%d\n", (S >> 2) & 1);       // 第 2 位：1
    printf("%d\n", S & (S - 1));        // 去掉最低位的 1 → 0b1000 = 8
    for (int T = S; T; T &= T - 1)      // 逐位遍历所有 1
        printf("%d ", __builtin_ctz(T));// 输出 2 3
    return 0;
}

#include <bits/stdc++.h>
using namespace std;

int main() {
    for (int S = 0; S < 8; ++S)
        printf("%d -> %d\n", S, __builtin_popcount(S));   // 0..3 个 1
    printf("%d\n", __builtin_popcountll(1LL << 40));      // 1（64 位里只有一个 1）
    printf("%d\n", __builtin_ctz(12));                    // 2（12 = 0b1100）

    int pc[8];                                            // 手写版：一遍递推
    pc[0] = 0;
    for (int S = 1; S < 8; ++S) pc[S] = pc[S >> 1] + (S & 1);
    printf("%d\n", pc[7]);                                // 3
    return 0;
}

#include <bits/stdc++.h>
using namespace std;

int main() {
    int mask = 0b1011;                        // 集合 {0, 1, 3}
    for (int sub = mask; sub; sub = (sub - 1) & mask)
        printf("%d(%d) ", sub, __builtin_popcount(sub));
    // 输出：11(3) 10(2) 9(2) 8(1) 3(2) 2(1) 1(1)
    printf("\n");
    return 0;
}

第一道题是状压 DP 的本体：n 个东西、每个只能取一次、要排一个最优顺序。先想清楚“暴力为什么必死”，再想“哪一部分信息其实没用”。

#include <bits/stdc++.h>
using namespace std;

int n;
double x[16], y[16];
double d[16][16];                  // d[i][j]：编号 i 与 j 的直线距离
double f[1 << 15][15];             // f[S][i]：已吃集合 S、最后一口在 i 的最小路程

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;
    x[0] = y[0] = 0;                               // 0 号点就是原点，当作起点
    for (int i = 1; i <= n; ++i) cin >> x[i] >> y[i];

    for (int i = 0; i <= n; ++i)                   // 两两距离只跟坐标有关，先算成表
        for (int j = 0; j <= n; ++j) {
            double dx = x[i] - x[j], dy = y[i] - y[j];
            d[i][j] = sqrt(dx * dx + dy * dy);     // 开方只做 (n+1)² 次，别放进转移里
        }

    int full = (1 << n) - 1;                       // 全部吃完的集合
    for (int S = 0; S <= full; ++S)
        for (int i = 0; i < n; ++i) f[S][i] = 1e18;   // 求最小，INF 要足够大

    for (int i = 0; i < n; ++i)
        f[1 << i][i] = d[0][i + 1];                // 第一口：从原点直接过去（注意 +1 的下标错位）

    for (int S = 1; S <= full; ++S)                // S 递增天然就是拓扑序
        for (int i = 0; i < n; ++i) {
            if (!(S >> i & 1)) continue;           // i 不在集合里，这个状态无意义
            for (int j = 0; j < n; ++j) {
                if (S >> j & 1) continue;          // j 已经吃过，不能重复吃
                int T = S | (1 << j);              // 新集合：把 j 加进去
                double nd = f[S][i] + d[i + 1][j + 1];
                if (nd < f[T][j]) f[T][j] = nd;    // 松弛
            }
        }

    double ans = 1e18;
    for (int i = 0; i < n; ++i) ans = min(ans, f[full][i]);
    printf("%.2f\n", ans);
    return 0;
}

第二类问题换了个问法：不问“最优”，问“有多少个”。n 可以到 10¹⁸，但位数只有 19 位——所以不枚举数，枚举“填法”。

#include <bits/stdc++.h>
using namespace std;

int a[15];              // n 的各位，低位在下标 1
long long f[15];        // f[pos]：还剩 pos 位、不顶格不限前导零时的填法数

long long dfs(int pos, bool limit, bool lead) {
    if (pos == 0) return 1;                                   // 填完了，一条填法
    if (!limit && !lead && f[pos] != -1) return f[pos];        // 自由身才查表
    int up = limit ? a[pos] : 9;                               // 顶格只能到上界
    long long res = 0;
    for (int d = 0; d <= up; ++d)
        res += dfs(pos - 1, limit && (d == up), lead && (d == 0));
    if (!limit && !lead) f[pos] = res;                         // 自由身才写表
    return res;
}

int main() {
    int n = 123, len = 0;
    for (int t = n; t; t /= 10) a[++len] = t % 10;              // 拆位，低位在前
    memset(f, -1, sizeof f);
    cout << dfs(len, true, true) << "\n";                       // 124 = n + 1，因为 0 也被数进去了
    return 0;
}

#include <bits/stdc++.h>
using namespace std;

int a[15];                 // n 的各位，a[1] 是个位
long long f[15][10];       // f[pos][prev]：还剩 pos 位、上一位是 prev 的自由填法数

// pos：还剩几位；prev：上一位数字；limit：是否贴住上界；lead：前缀是否全 0
long long dfs(int pos, int prev, bool limit, bool lead) {
    if (pos == 0) return 1;                                   // 每一位都填完了
    if (!limit && !lead && f[pos][prev] != -1) return f[pos][prev];
    int up = limit ? a[pos] : 9;                               // 顶格时最多到上界那一位
    long long res = 0;
    for (int d = 0; d <= up; ++d) {
        if (!lead && abs(d - prev) < 2) continue;              // 不是首位，且与上一位差不足 2
        res += dfs(pos - 1, d, limit && (d == up), lead && (d == 0));
    }
    if (!limit && !lead) f[pos][prev] = res;                   // 只有自由身才写表
    return res;
}

long long solve(int n) {
    if (n < 0) return 0;
    int len = 0;
    while (n) { a[++len] = n % 10; n /= 10; }
    return dfs(len, 0, true, true);       // n = 0 时 len = 0，dfs 立刻返回 1，正好把 0 数上
}

int main() {
    int A, B;
    cin >> A >> B;
    memset(f, -1, sizeof f);
    cout << solve(B) - solve(A - 1) << "\n";   // 0 在两边各出现一次，相减自动抵消
    return 0;
}

#include <bits/stdc++.h>
using namespace std;

int n, m;
int clrMask[105], setMask[105];   // 每个按钮翻译成的两个掩码
int dist[1 << 10];                // dist[S]：从“全亮”走到 S 最少按几次

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m;
    for (int i = 1; i <= m; ++i)
        for (int j = 0; j < n; ++j) {
            int a;
            cin >> a;
            if (a == 1) clrMask[i] |= 1 << j;         // 按完这盏一定是灭 → 记住“要清掉”
            else if (a == -1) setMask[i] |= 1 << j;   // 按完这盏一定是亮 → 记住“要置上”
            // a == 0：这一位两边都不记，按完保持不变
        }

    int full = (1 << n) - 1;          // 初始：所有灯都亮
    memset(dist, -1, sizeof dist);    // −1 同时表示“没访问过”，省掉 vis 数组
    queue<int> q;
    dist[full] = 0;
    q.push(full);

    while (!q.empty()) {
        int S = q.front();
        q.pop();
        if (S == 0) break;            // 已经全灭，不用再扩展
        for (int i = 1; i <= m; ++i) {
            int T = (S & ~clrMask[i]) | setMask[i];   // 一次位运算完成“该灭的灭、该亮的亮”
            if (dist[T] == -1) {                      // 每个状态只入队一次
                dist[T] = dist[S] + 1;
                q.push(T);
            }
        }
    }

    cout << dist[0] << "\n";          // 走不到就是 −1，正好是题目要的输出
    return 0;
}