CodechiefSCDP

Ameiyo · 2019-07-19 08:12:46 · 个人记录

状压DP不多的习题及其思路

made\ by\ Ameiyo

题目链接

参考翻译 (其实大部分题目都有中文题面)
A:CodeChef TSHIRTS
B:CodeChef MAXOR
C:CodeChef SHOPTRIP
D:CodeChef DIGITLIS
E:CodeChef GEEK04
F:CodeChef SEQLCS
G:CodeChef WGME
H:CodeChef RRSERVER
I:CodeChef INSQ16C
J:CodeChef CHEFSHOP
K:CodeChef FAVGAME
L:CodeChef SEAKAM
M:CodeChef ZUBWALLT
N:CodeChef NPLANAR
O:CodeChef FSFSFS
P:CodeChef CHEFCLOS

解析

A

每件T恤去找一个没有穿衣服的人，定义 f[i][S] 表示前 i 件衣服， S 所表示的穿衣情况的方案数，那么就有

f[i][S\ |\ x] += f[i - 1][S] (x \notin S)

然后直接DP就行了，注意输入有一点点麻烦。

B

一道很棒的题目，用到了一个东西叫高维前缀和。

(不知道是不是因为有点冷门的原因，目前找的题目较少，由于时间问题博主暂时没看，如果在看更多例题之前还没有明白的话可以QQ找我嘤嘤嘤)

题目的意思应该很容易发现，就是找到二进制位中 A[i] \in A[j] 的对数，直接 DP 会 TLE ，所以要用高维前缀和。

设 F[i] 表示属于 i 的子集的个数， G[i] 表示 i 的个数，因为同样的数里面每一对只能算一次，所以每个 i 对答案的贡献就是

G[i] \times (G[i] - 1) / 2 + (F[i] - G[i]) * G[i]

(因为就是上面博客的第一个例题，代码也有，就不细讲了)

C

用 f[k][S] 表示最后停留在 k ，而且已经买了 S 的食材，所需的最小步数，转移时枚举 n + 1 个地点(包括厨房)。

复杂度 O(T * n ^ 2 * 2 ^ k) \leq O(53084160) ，应该不会TLE。

虽然说觉得这种状压挺常见的，但我自己还是WA了好几次，所以放上代码。

int Get() {
    string s; cin >> s;
    int res = 0;
    for (reg int i = 0; i < m; ++i) res += (s[i] ^ 48) * (1 << i);
    return res;
}

double GET(int x, int y) {
    return sqrt((X[x] - X[y]) * (X[x] - X[y]) + (Y[x] - Y[y]) * (Y[x] - Y[y]));
}

void scan();
int _main() {
    int T = read<int>();
    for (int kas = 1; kas <= T; ++kas) {
        n = read<int>(), m = read<int>();
        for (reg int i = 0; i <= n; ++i) for (reg int j = 0; j < (1 << m); ++j) f[i][j] = INF;
        for (reg int i = 1; i <= n; ++i) X[i] = read<int>(), Y[i] = read<int>();
        for (reg int i = 1; i <= n; ++i) W[i] = Get();
        f[0][0] = 0.0;
        for (reg int j = 0; j < (1 << m); ++j)
            for (reg int i = 0; i <= n; ++i)
                for (reg int k = 0; k <= n; ++k)
                    f[k][j | W[k]] = min(f[k][j | W[k]], f[i][j] + GET(i, k));
        if (f[0][(1 << m) - 1] == INF) puts("-1");
        else printf("%.10f\n", f[0][(1 << m) - 1]);
    }
    return 0;
}

(觉得自己好像有点懒)

D

这个最长上升子序列没见过真是想不到。。。。

先要看到每个数都是 0 ~ 9 ，所以数组也是 1 ~ 10 的。

首先考虑我们的最长上升子序列有什么可以压缩成状态然后辅助我们转移的。

先想最原始的暴力DP打法：每次在前面找一个键值小于自己的数中最大的权值(其实就是可以转移过来的答案里面最大的，满足最长性质，或者说最优子结构)，然后继续找。。。

看起来好像没有什么可以用来压缩的东西。

再看看 log 级别的算法：

因为权值的更新是建立在值域上，而且只会往大更新，所以树状数组和线段树都可以维护，但是每个数上的值都可以达到 10 ，压缩之后就会达到 10 ^ { 10 } = 10000000000 ，显然是吃不消的。

但是如果我们思考一下树状数组的工作路程(其实线段树类似，只是 Fenwick\ Tree 较轻量级)：

查询小于当前的数中最大的权值 x 。
然后用 x + 1 去更新比当前的数更大的数。

我们会发现这样下来，如果每次暴力去更新，也就是 O(10) 更新 O(1) 查询的话，那么数组中的值都将是保证递增的。

那又怎样，值域不还是 10 ! ！！

(自己拆自己台嘤嘤嘤)

但是在递增的过程中，有一个关键的性质：

前后两个权值，要么相等，要么多一。

所以我们压缩的是辅助数组的差分数组。

关于性质的证明：

首先肯定不会减少，因为一个值是被比他小的数更新过的。

而且差值肯定不会大于等于 2 ，否则，因为一个值 g[t] 是从比他小的数更新过来的，那么就肯定存在一个比 t 小的数 b 其值 g[b] = g[t] - 1 ，即二者差值为 1 ，但是 g[t] - g[t - 1] \geq 2 ，那么 b 就肯定小于 t - 1 ，也就是说 g[b] = g[t] - 1 > g[t] - 2 \geq g[t - 1] ，这就不满足递增的性质，矛盾。

证毕。

为了方便讲解，我们在下面的描述中都使用 辅助数组(注意不是差分数组！！！) 来推导DP的转移。

假设在题目给出的数组中，当前数字为 A ，那么我们对于某个辅助数组 g ，对于所有满足 g[x - 1] = A - 1 的 x ，就某个对应于 g 的排列 (即其辅助数组与 g 相同) 而言，在第 i 位放 x 就满足了以 i 这个数字结尾的最长上升子序列长度为 A ，因为 g'[x] = A ，也就是说新的辅助数组 g' 的方案数可以从 g 中转移过去。

而新的辅助数组是怎样的呢，其实就是把所有 g[y] = A - 1 并且 y \geq x 的 g[y] 都改成 g'[y] = A 就是新的辅助数组。

那差分数组更新之后又是怎样的呢？

原来的 g[t] = A 而 g[t - 1] = A - 1 ，那么 d[t] = g[t] - g[t - 1] = 1 ，而且 x 到 t - 1 差分数组都是 0 。

更新之后 g'[t] = A , g'[t - 1] = A 且 g'[x] = A, g'[x - 1] = A - 1 ，所以 d'[t] = 0, d'[x] = 1 就是唯二的修改。

在实现上因为非 0 即 1 ，所以用常见的二进制压缩状态即可。

细节可以见代码。

memset(f, 0, sizeof f);
f[0][0] = 1;
n = read<int>();
for (reg int i = 1; i <= n; ++i) {
    int A = read<int>();
    for (reg int j = 0; j < 1024; ++j) {
        int res = 0, tp = (i == 1 && n != 1 ? 0 : -1), tpx = 0;
        for (reg int k = (i == 1 && n != 1 ? 1 : 0); k <= 9 && res < A; ++k) {
            if (j & (1 << k)) ++res, tpx = tp, tp = k;
            if (res == A) for (reg int l = tpx + 1; l <= k; ++l)
                (f[i][(j ^ (1 << k)) | (1 << l)] += f[i - 1][j]) %= Mod;
            // 注意这里是在 res == A 时就转移，因为只要把这一位变成 A 即可
            // 而不是所有数组中最大的那一位
            // 实在想不明白可以回归本真，在更新的时候是怎么操作的
            // 我写题解的时候倒在这里卡了一会
        }
        if (res == A - 1) for (reg int l = tp + 1; l <= 9; ++l)
            // 如果最大的只有 A - 1 ，一样可以
            f[i][j | (1 << l)] = (f[i][j | (1 << l)] + f[i - 1][j]) % Mod;
    }
}
int Ans = 0;
for (reg int i = 0; i < 1024; ++i) Ans = (Ans + f[n][i]) % Mod;
cout << Ans << endl;

(事实上，我个人在写题解的时候不喜欢把细节点出来，因为这种实现上的问题有时候提出来就和剧透一般，令人讨厌，这点与看到一道题没有想就直接听别人讲或者看题解我觉得是一样的)

E

博主打的是全贪心。。。状压的做法可以见 orangejuice的博客，不过他好像很懒，打的不是很详细。

全贪心的做法看这个博客，讲的很详细。这里只给出代码：

n = read<int>();
for (reg int i = 1; i <= n; ++i) A[i] = read<int>();
sort(A + 1, A + n + 1);
int Ans = 0;
for (reg int i = n; i > 3; i -= 2)
    Ans += min(A[i] + A[2] * 2 + A[1], A[i] + A[i-1] + A[1] * 2);
if (n & 1) Ans += A[1] + A[3];
if (n == 1) Ans = A[1];
else Ans += A[2];
// 记得要特判
cout << Ans << endl;

F

看到这道对 DP 进行 DP 的题目，我有想起了上面那道 D 题。

没错， 最长公共子序列 也是一道非常经典的 DP 问题，这里同样默认读者已经学习过 最长公共子序列的算法 。

借鉴一下 D 题，猜测这次状压的也是辅助数组。

回想一下，我们在做最长公共子序列的时候：

我们已经知道了 A ，假设已经得到了 f[i][j] (i <= n, j <= m < n) ，也就是说 B 的前 m 位已与 A 的全部计算过，现在给出 B[m + 1] ，就可以得到新的 f[i][m + 1] (i <= n) ，而通过上面的公式我们可以看到 f[i][m + 1] 和 f[i - 1][m + 1] 之间的差值 非零即一 ，那么同 D 题，我们就可以压缩这个差值。

用 f[i][j] 表示 B 的前 i 位与 A 计算得到的辅助数组为 j 时的方案数， nex[j][l] 表示在 B[i + 1] 这一位放 l 所得到的辅助数组，那么转移就是

f[i + 1][nex[j][l]] += f[i][j]

其中 l 是放在 B[i + 1] 上的数。

计算 nex[j][l] 的复杂度是 O(n) ，那么总复杂度就是 O(n * 2 ^ n * k * n) = O(n ^ 3 * 2 ^ n) \leq O(268435456) ，时间超限。

实际上， nex[j][l] 是可以预处理的，那么时间复杂度就变成了 O(2 ^ n * k + n * 2 ^ n * k) = O(n ^ 2 *2 ^ n) \leq O(16777216) ，算上多组数据 4 秒应该吃得下。

剩下的关键就是在预处理上。用 g[] 表示原来的辅助数组 j ，用 d[] 表示新的辅助数组 nex[j][l] 。

那么直接 "解压" 给 g[] ，然后再算出 d[] ，接着 "压缩" 回 nex[j][l] 即可。

代码

n = read<int>(), k = read<int>(), L = read<int>();
for (reg int i = 1; i <= n; ++i) A[i] = read<int>();
for (reg int i = 0; i < (1 << n); ++i) {
    int g[N] = { 0 }, d[N] = { 0 };
    for (reg int j = 0; j < n; ++j) g[j + 1] = g[j] + ((i >> j) & 1);
    for (reg int j = 1; j <= k; ++j) { // 选 j 这个数
        d[0] = nex[i][j] = 0;
        for (reg int l = 1; l <= n; ++l) d[l] = (A[l] == j ? g[l - 1] + 1 : max(d[l - 1], g[l]));
        for (reg int l = 0; l < n; ++l) nex[i][j] |= (1 << l) * (d[l + 1] - d[l]);
    }
}
memset(f, 0, sizeof f);
f[0][0] = 1;
for (reg int i = 0; i < n; ++i) {
    for (reg int j = 0; j < (1 << n); ++j) {
    if (f[i][j] > 0) for (reg int l = 1; l <= k; ++l)
        f[i + 1][nex[j][l]] = (f[i + 1][nex[j][l]] + f[i][j]) % Mod;
    }
}
int Ans = 0;
for (reg int j = 0; j < (1 << n); ++j)
if (Cal(j) == L) Ans = (Ans + f[n][j]) % Mod;
cout << Ans << endl;

G

不知道该怎么说。。。

先预处理出所有的情况(对于十个字母而言)下输与赢得局面。

然后就是 DP ？

每次决策的时候有点贪心，如果能让对方必输，就让他必输；否则就是自己必输，因为没有平局。

所以记搜或是循环其实都无所谓的，反正也很小。

H

一道很好的 DP 。

我们按照从左到右的顺序把点一个个排起来，那么每次的决策就是选择一个没排好的点放在当前排好的点右边。

所以可以将所有的点分成两部分，用集合 S 表示这些点已经在左边，剩下的就是没放过的点。

对于某个可以由 S 到达的最终状态，也就是 所有在 S 中的点都处于不在 S 的点的左边 的某个状态来说，其中有 m 条边，我们把两个点不是都在 S 中的边画出来，就会发现在 S 这个状态下，不管之后的点如何排列，都只有这些边会经过新的点前面之一小段(权值为 1 )，即只有这些边会做出贡献。

举个栗子：

在上图中黑线左边的点是已经放了的，右边的 3, 4, 5 是还没有放的。

可以发现，不论 3, 4, 5 如何排列，会经过黑线的边都只有 (1, 3), (1, 4) ，那么对黑线这个位置贡献了 1 点权值的也只有 (1, 3), (1, 4) ，也就是说， 当 S 确定之后，做出新决策的时候加入的权值是确定的 。

感觉没讲清楚。。。可以找一些别的例子来考虑一下吧。。。

也可以对着代码理解嘤嘤嘤。

n = read<int>(), m = read<int>();
for (reg int i = 1, a, b; i <= m; ++i) {
    a = read<int>() - 1, b = read<int>() - 1;
    w[a] |= (1 << b), w[b] |= (1 << a);
}
Uplim = (1 << n) - 1;
for (reg int i = 1; i <= Uplim; ++i) cnt[i] = cnt[i >> 1] + (i & 1);
memset(f, 0x3f, sizeof f);
f[0] = 0;
for (reg int i = 0; i < Uplim; ++i) {
    int sum = f[i];
    for (reg int j = 0; j < n; ++j)
        if (i & 1 << j) sum += cnt[(~i) & w[j]];
    for (reg int j = 0; j < n; ++j)
        if (~i & 1 << j) f[i | (1 << j)] = min(f[i | (1 << j)], sum);
    // 其实平时位运算的时候要小心。。。这里只是偷懒而已
}
cout << f[Uplim] << endl;

I

因为是完全二叉树，所以太简单了，懒得打。。。

如果有人想要题解，去这个博客看看吧。。。

~~不行我真的是太懒了嘤嘤嘤~~

惊奇的发现他用的是 DSU ，而我是先深搜，再二分。

所以还是放代码。

void Dfs(int x) {
    if ((x << 1) <= n) Dfs(x << 1);
    if ((x << 1 | 1) <= n) Dfs(x << 1 | 1);
    for (reg int i = 1; i <= 17; ++i) f[x][i] = f[x << 1][i - 1] | f[x << 1 | 1][i - 1];
    // 这个数组有倍增的想法
    // f[i][j] = (i 往下 2 ^ j 的高度里包含的颜色)
}

n = read<int>();
memset(f, 0, sizeof f);
for (reg int i = 1; i <= n; ++i)
    f[i][0] = (1 << (read<int>() - 1));
Dfs(1);
for (reg int i = 1; i <= n; ++i)
    for (reg int j = 1; j <= 17; ++j)
        f[i][j] |= f[i][j - 1];
// 因为要二分
m = read<int>();
for (reg int i = 1, a, b; i <= m; ++i) {
    a = read<int>(), b = read<int>();
    int l = 0, r = 17, Ans = -1, mid;
    while (l <= r) {
        mid = (l + r) >> 1;
        if (cnt[f[a][mid]] >= b) {
            // cnt[x] = x 里面 1 的个数
            Ans = mid;
            r = mid - 1;
        } else {
            l = mid + 1;
        }
    }
    printf("%d\n", Ans);
}

J

因为每个食材都要买，所以可以把问题转化成免费的物品的最大价值。

把所有的价格从小到大一行排开，我们要做的就是用一些套餐不重复的覆盖这些价格，并且使每个套餐中最小的价格的和最大。

转移有贪心的想法。

大致上就是说