【题目链接】:http://codeforces.com/problemset/problem/417/D

【题意】



有n个人共同完成m个任务;

每个人有可以完成的任务集(不一定所有任务都能完成);

(有重叠也无所谓);

然后它完成这些任务需要报酬xi;

同时它需要特殊物品的数量达到ki才会愿意去做这些任务;

这样特殊物品的单价为b;

然后问你完成这m个任务需要花费多少钱.

【题解】



假设我们最后选了几个人;

它们能够完成m项任务;

则这个特殊物品的数量应该是这些人里面ki的最大值;

根据这个;

我们一开始先把所有人的信息按照ki升序排;

然后做状态压缩DP;

设dp[i]表示完成任务的情况为i(用二进制表示)的最小花费;

则按照顺序选择;

如果在某一时刻;

dp[2m−1]有值了(或者发生了改变);

则可以直接用它+a[i].k*b来更新答案;

因为此时肯定是因为选择了第i个人,所以才发生了变化;

而又因为是升序排的,所以肯定是这个人的k值最大;

所以特殊物品的数量就是选择它啦.>_<

最后的答案大于1018QAQ



【Number Of WA】



1



【完整代码】

#include <bits/stdc++.h>

using namespace std;

#define lson l,m,rt<<1

#define rson m+1,r,rt<<1|1

#define LL long long

#define rep1(i,a,b) for (int i = a;i <= b;i++)

#define rep2(i,a,b) for (int i = a;i >= b;i--)

#define mp make_pair

#define pb push_back

#define fi first

#define se second

#define ms(x,y) memset(x,y,sizeof x)

#define Open() freopen("D:\\rush.txt","r",stdin)

#define Close() ios::sync_with_stdio(0),cin.tie(0)

typedef pair<int,int> pii;

typedef pair<LL,LL> pll;

const int dx[9] = {0,1,-1,0,0,-1,-1,1,1};

const int dy[9] = {0,0,0,-1,1,-1,1,-1,1};

const double pi = acos(-1.0);

const int M = 110e4;

const int N = 1e2+10;

struct abc{

    int x,k,sta;

};

int temp,n,m;

LL dp[M],b,ans = -1;

abc a[N];

int main(){

    //Open();

    Close();//scanf,puts,printf not use

    //init??????

    cin >> n >> m >> b;

    rep1(i,1,n){

        int num;

        cin >> a[i].x >> a[i].k >> num;

        rep1(j,1,num){

            int x;

            cin >> x;

            a[i].sta |= (1<<(x-1));

        }

    }

    sort(a+1,a+1+n,[&](abc a,abc b){ return a.k<b.k;});

    int ma = 1<<m;

    ms(dp,-1);

    dp[0] = 0;

    rep1(i,1,n){

        rep1(j,0,ma-1){

            if (dp[j]==-1) continue;

            int status = j | a[i].sta;

            if (dp[status]==-1){

                dp[status] = dp[j]+a[i].x;

            }

            else

                dp[status] = min(dp[status],dp[j]+a[i].x);

        }

        if (dp[ma-1]!=-1){

            if (ans==-1){

                ans = dp[ma-1]+b*a[i].k;

            }

            else

                ans = min(ans,dp[ma-1]+b*a[i].k);

        }

    }

    if (ans==-1)

        cout <<-1<<endl;

    else

        cout << ans << endl;

    return 0;

}