# B 筱玛爱阅读
B 筱玛爱阅读
题目地址
题意：给定n个物品，m个方案，第i个方案包含个物品，现在共有n个价格，但不确定每一个物品属于哪一个价格。问买下所有物品需要的最小价格。
分析：
1. 简化问题，加入价格固定，就是一个状压dp，如果暴力递推，那么复杂度，不可接受，考虑采用枚举子集的方式复杂度
2. 现在考虑价格不固定，先把物品从大到小排序，考虑新加入的最后一个子集优惠的是最后一个元素即可
参考代码：
#include
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;
} 
