链接：https://ac.nowcoder.com/acm/contest/946/B
来源：牛客网
 

筱玛爱阅读

时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 262875K，其他语言525750K
64bit IO Format: %lld

题目描述

筱玛是一个热爱阅读的好筱玛，他最喜欢的事情就是去书店买书啦！

一天，他来到一家有nn本书的书店，筱玛十分快乐，决定把这家店里所有的书全部买下来。

正巧今天店里在搞促销活动，包含若干个促销方案。每个促销方案是由指定的若干本书构成的集合，如果购买了该方案中所有的书，那么其中最便宜的一本书将免费。但是，每本书只能用于一个促销方案。

作为店里的VIP，筱玛会得到nn个价格标签。筱玛可以给每本书挑选一个价格标签，使得每个价格标签和每本书一一对应。

筱玛想要知道，在合理利用所有促销方案的情况下，买下所有书最小要多少钱。

 

输入描述:


 

第一行两个数n,mn,m，分别表示书的本数和促销方案的种数。

第二行nn个整数，表示每个价格标签上的标注的价格。

接下来mm行，每行第一个数kk表示该促销方案包含书的数量。接下来kk个数，表示书的编号。

输出描述:

输出一行一个数，表示答案。

示例1

输入

复制

4 2
2 3 2 4
2 2 3
2 2 4

输出

复制

8

备注:


 

对于100%的数据，1≤n≤15,1≤m≤2n−11≤n≤15,1≤m≤2n−1，所有标签价值之和在intint范围内。

、

子集DP

预处理cnt[i]  为 i  的二进制中1的数目

dp[i]为购买状态为i的书的最大优惠  

cost  先排序

每个方案贪心取最大

添加j方案   i^j是原来的方案  加上可选的最大的  cost  更新

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=(1<<15)+12;
int cost[20];
int num[maxn];
vector<int>v[maxn];
int flag[maxn];
int dp[maxn];
int cnt[maxn];
int main()
{
    int n,m,x;
    cin>>n>>m;
    ll sum=0;
    for(int i=1; i<=n; i++)
    {
        scanf("%d",&cost[i]);
        sum+=cost[i];
    }
    sort(cost+1,cost+n+1,greater<int>());
    for(int i=1; i<=m; i++)
    {
        scanf("%d",&num[i]);
        for(int j=1; j<=num[i]; j++)
        {
            scanf("%d",&x);
            v[i].push_back(x);
        }
        int mi=cost[v[i][0]];
        int tp=0;
        for(int j=0; j<v[i].size(); j++)
        {
            mi=min(cost[v[i][j]],mi);
            tp|=(1<<(v[i][j]-1));
        }
       flag[tp]=1;//标记可更新套餐
    }
    int ma=1<<n;
    for(int i=1;i<ma;i++)
        cnt[i]=cnt[(i&(i-1))]+1;//求二进制中i中1的位数
    ll ans=sum;
    for(int i=0; i<ma; i++)
    {
        int s=i;
        for(int j=s;j;j=(j-1)&s)
        {
            if(flag[j])
            {
                dp[i]=max(dp[i],dp[i^j]+cost[cnt[i]]);//更新
            }
        }
        ans=min(ans,sum-dp[i]);
    }
    cout<<ans;
    return 0;
}