原题链接
小图非常想参加“俄罗斯密码杯”的决赛，或者至少能拿到一件 T-shirt 衫。但是比赛的题目太复杂了，所以他和 n 个朋友商量，帮他解决问题。比赛一共有 m 道题。小图知道每个朋友能解决的题目。但是他的朋友不会提供无偿帮助：第 i 个朋友要求小图支付 xi 元钱。另外还要求小图的电脑至少要连接 ki 个显示器，每个显示器的价格是 b 元钱。
小图对钱很谨慎，所以他想花尽可能少的钱来解决所有的问题。请你帮一帮小图，告诉他最少花多少元钱能解决所有题目。注意，一开始没有显示器连接到小图的电脑。
Input
第一行输入三个整数 n, m, b (1 ≤ n ≤ 100; 1 ≤ m ≤ 20; 1 ≤ b ≤ 109)，分别表示小图的朋友数量，问题的数量和一台显示器的成本。
接下来输入的 2n 行数据描述了这些朋友各自的要求。第 2i 和 (2i + 1) 行包含关于第 i 个朋友的信息。第 2i 行包含三个整数 xi, ki 和 mi (1 ≤ xi ≤ 109; 1 ≤ ki ≤ 109; 1 ≤ mi ≤ m)，分别表示该朋友想要的钱数，监视器个数和他可以解决的问题的数量。第 (2i + 1) 行包含 mi 个不同的正整数，表示第 i 个朋友可以解决的问题的编号。问题的编号从 1 到 m。
Output
输出小图解决所有题目要花费的最少的钱。
如果没有满足条件的结果，请输出 -1。
Examples
Input
2 2 1
100 1 1
2
100 2 1
1
Output
202
Input
3 2 5
100 1 1
1
100 1 1
2
200 1 2
1 2
Output
205
Input
1 2 1
1 1 1
1
Output
-1
思路：
m的范围很小，考虑用二进制来表示某个问题是否被解决.
dp[i]表示状态为i时不包括显示器费用的最小花费，这样只需要枚举每个朋友可以转移哪些状态即可。
对每个朋友所需的显示器数量进行排序，这样枚举到第i个人时，所需的显示器费用是固定的。
爆ll了，要开ull.
代码：
#pragma GCC optimize(2) #include<bits/stdc++.h> using namespace std; typedef long long ll; typedef unsigned long long ull; typedef pair<ll,ll>PLL; typedef pair<int,int>PII; typedef pair<double,double>PDD; #define I_int ll inline ll read() { ll x=0,f=1; char ch=getchar(); while(ch<'0'||ch>'9') { if(ch=='-')f=-1; ch=getchar(); } while(ch>='0'&&ch<='9') { x=x*10+ch-'0'; ch=getchar(); } return x*f; } #define read read() #define closeSync ios::sync_with_stdio(0);cin.tie(0);cout.tie(0) #define multiCase int T;cin>>T;for(int t=1;t<=T;t++) #define rep(i,a,b) for(int i=(a);i<=(b);i++) #define repp(i,a,b) for(int i=(a);i<(b);i++) #define per(i,a,b) for(int i=(a);i>=(b);i--) #define perr(i,a,b) for(int i=(a);i>(b);i--) ll ksm(ll a,ll b,ll p) { ll res=1; while(b) { if(b&1)res=res*a%p; a=a*a%p; b>>=1; } return res; } #define PI acos(-1) #define x first #define y second const int maxn=1e6+7,inf=0x3f3f3f3f; struct node{ ull x,k,m; ull s; }a[110]; bool cmp(node a,node b){ return a.k<b.k;///排序后枚举到第i个所需的显示器数量就是总的数量 } ull dp[1<<21];///dp[i]表示当前状态是i时，所需要的最小花费（不计算显示器的花费） int main() { int n=read,m=read,b=read; for(int i=1;i<=n;i++){ cin>>a[i].x>>a[i].k>>a[i].m; for(int j=0;j<a[i].m;j++){ ull t;cin>>t; a[i].s|=1<<t-1;///记录每个人能够解决的问题数 } } sort(a+1,a+1+n,cmp); dp[0]=0; for(int i=1;i<(1<<m);i++) dp[i]=1e19; ull res=1e19; for(int i=1;i<=n;i++){ for(int j=0;j<(1<<m);j++) dp[j|a[i].s]=min(dp[j|a[i].s],dp[j]+a[i].x); res=min(res,dp[(1<<m)-1]+a[i].k*b); } if(res==1e19) puts("-1"); else cout<<res<<endl; return 0; }
