A boy named Gena really wants to get to the "Russian Code Cup" finals, or at least get a t-shirt. But the offered problems are too complex, so he made an arrangement with hisnfriends that they will solve the problems for him.
The participants are offeredmproblems on the contest. For each friend, Gena knows what problems he can solve. But Gena’s friends won’t agree to help Gena for nothing: thei-th friend asks Genaxirubles for his helpin solving all the problemshe can. Also, the friend agreed to write a code for Gena only if Gena’s computer is connected to at leastkimonitors, each monitor costsbrubles.
Gena is careful with money, so he wants to spend as little money as possible to solve all the problems. Help Gena, tell him how to spend the smallest possible amount of money. Initially, there’s no monitors connected to Gena’s computer.
Input
The first line contains three integersn,mandb(1≤n≤100;1≤m≤20;1≤b≤109)— the number of Gena’s friends, the number of problems and the cost of a single monitor.
The following2nlines describe the friends. Lines number2iand(2i+1)contain the information about thei-th friend. The2i-th line contains three integersxi,kiandmi(1≤xi≤109;1≤ki≤109;1≤mi≤m)— the desired amount of money, monitors and the number of problems the friend can solve. The(2i+1)-th line containsmidistinct positive integers— the numbers of problems that thei-th friend can solve. The problems are numbered from1tom.
Output
Print the minimum amount of money Gena needs to spend to solve all the problems. Or print -1, if this cannot be achieved.
Sample test(s)
input
2 2 1100 1 12100 2 11
output
202
input
3 2 5100 1 11100 1 12200 1 21 2
output
205
input
1 2 11 1 11
output
-1
我们发现由于所需要的监视器数量不同，，所以我们要将监视器数量从小到大
排序，然后状压DP，因为后面所需监视器超过前面，所以我们不必再考虑监
视器够不够。接下来就是状压DP了。
#include<cstdio>#include<cstring>#include<algorithm>#include<vector>#include<string>#include<iostream>#include<queue>#include<cmath>#include<map>#include<stack>#include<bitset>using namespace std;#define REPF( i , a , b ) for ( int i = a ; i <= b ; ++ i )#define REP( i , n ) for ( int i = 0 ; i < n ; ++ i )#define CLEAR( a , x ) memset ( a , x , sizeof a )typedef long long LL;typedef pair<int,int>pil;const LL INF=1e19;LL dp[1<<20];struct node{int cost,k;int s;}e[110];int n,m,b,num;int cmp(node l1,node l2){return l1.k<l2.k;}int main(){int x;while(~scanf("%d%d%d",&n,&m,&b)){CLEAR(dp,-1);REPF(i,1,n){scanf("%d%d%d",&e[i].cost,&e[i].k,&num);while(num–){scanf("%d",&x);e[i].s|=(1<<(x-1));}}dp[0]=0;LL ans=INF;int mm=(1<<m)-1;sort(e+1,e+n+1,cmp);REPF(i,1,n){for(int st=0;st<=mm;st++){if(dp[st]==-1) continue;int status=st|e[i].s;if(dp[status]==-1) dp[status]=dp[st]+e[i].cost;else dp[status]=min(dp[status],dp[st]+e[i].cost);}if(dp[mm]!=-1)ans=min(ans,dp[mm]+1LL*e[i].k*b);}if(ans==INF) printf("-1\n");else printf("%lld\n",ans);}return 0;}
接受自己的失败面，是一种成熟，更是一种睿智
