AcWing 5383. 收集饰品

传送门：5383. 收集饰品

思路

背包dp + 状压dp，非常巧妙的做法

现按照 k 从小到达排序，将每个饰品看成一个二进制位，每个宝箱可以让几个二进制位为 1，现在问题变成，选择若干宝箱，让每个二进制位变成 1 的最小花费，这是个典型的背包。

状态转移方程：

$$ dp[j | mask[i]] = std::min(dp[j | mask[i]], dp[j] + x[i]); $$

复杂度：$O(n2^m)$

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
/**
 *    author:  jujimeizuo
 *    created: 2024-01-06 20:35:26
**/
##include "bits/stdc++.h"

##ifdef LOCAL
##include "algo/debug.h"
##else
##define debug(...) 42
##endif

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

    int n, m, b;
    std::cin >> n >> m >> b;
    std::vector<int> x(n), k(n), mask(n);
    for (int i = 0; i < n; i += 1) {
        int cnt;
        std::cin >> x[i] >> k[i] >> cnt;
        for (int j = 0; j < cnt; j += 1) {
            int id;
            std::cin >> id;
            mask[i] = 1 << (id - 1);
        }
    }

    std::vector<int> order(n);
    std::iota(order.begin(), order.end(), 0);
    std::sort(order.begin(), order.end(), [&](int i, int j) {
        return k[i] < k[j];
    });

    constexpr static int64_t inf = std::numeric_limits<int64_t>::max() / 2;
    int64_t ans = inf;
    std::vector<int64_t> dp(1 << m, inf);
    dp[0] = 0;

    for (int i = 0; i < n; i += 1) {
        for (int j = 0; j < 1 << m; j += 1) {
            dp[j | mask[order[i]]] = std::min(dp[j | mask[order[i]]], dp[j] + x[order[i]]);
        }
        ans = std::min(ans, dp[(1 << m) - 1] + int64_t(1) * k[order[i]] * b);
    }

    if (ans == inf) {
        ans = -1;
    }

    std::cout << ans << std::endl;

    return 0;
}

本文作者：jujimeizuo
本文地址： https://blog.jujimeizuo.cn/2024/01/06/acwing-5383/
本博客所有文章除特别声明外，均采用 CC BY-SA 3.0 协议。转载请注明出处！