B 筱玛爱阅读

题目地址
题意：给定n个物品，m个方案，第i个方案包含 k i k_i ki​个物品，现在共有n个价格，但不确定每一个物品属于哪一个价格。问买下所有物品需要的最小价格。
分析：

  1. 简化问题，加入价格固定，就是一个状压dp，如果暴力递推，那么复杂度 O ( 2 n ∗ m ) = O ( 4 n ) O(2^n*m) = O(4^n) O(2n∗m)=O(4n)，不可接受，考虑采用枚举子集的方式复杂度 O ( 3 n ) O(3^n) O(3n)
  2. 现在考虑价格不固定，先把物品从大到小排序，考虑新加入的最后一个子集优惠的是最后一个元素即可

参考代码：

#include<bits/stdc++.h>
 
 
using namespace std;
 
// 1 排序，从大到小
// 2 状压方案
// 3 枚举子集
const int maxn = 1 << 16;
int a[maxn];
int num[maxn], plan[maxn];
bool vis[maxn];
int dp[maxn];
int main(void) {
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; ++i)
        cin >> a[i];
    sort(a + 1, a + n + 1);
    reverse(a + 1, a + n + 1);
    for (int i = 1; i <= m; ++i) {
        int k;
        scanf("%d", &k);
        for (int j = 1; j <= k; ++j) {
            int a; scanf("%d", &a);
            plan[i] |= 1 << (a - 1);
        }
        vis[plan[i]] = k;
    }
    for (int i = 0; i < (1 << n) - 1; ++i)
        num[i] = __builtin_popcount(i);
    int M = 0;
    for (int i = 1; i < (1 << n) - 1; ++i) {
        if (vis[i])
            dp[i] = max(dp[i], a[num[i]]);
        for (int s = i; s != 0; s = (s - 1)&i) {
            int x = i ^ s;
            if (!vis[x]) continue;
            dp[i] = max(dp[i], dp[s] + a[num[i]]);
        }
        for (int j = 0; j < n; ++j)
            dp[i | (1 << j)] = max(dp[i | (1 << j)], dp[i]);
        M = max(M, dp[i]);
    }
    int sum = 0;
    for (int i = 1; i <= n; ++i)
        sum += a[i];
 
 
    cout << sum - M << endl;
 
 
 
    return 0;
}

类似题目

  1. Sharing Chocolate UVALive - 4794
  2. Hackers’ Crackdown UVA - 11825