传送门：5383. 收集饰品

思路

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

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

状态转移方程：

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

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

Code

/**
 *    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;
}