Cunning Gena - Codeforces 417D

https://codeforces.com/problemset/problem/417/D

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 his n friends that they will solve the problems for him.

The participants are offered m problems 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: the i-th friend asks Gena xi rubles for his help in solving all the problems he can. Also, the friend agreed to write a code for Gena only if Gena's computer is connected to at least ki monitors, each monitor costs b rubles.

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 integers n, m and b (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 following 2n lines describe the friends. Lines number 2i and (2i + 1) contain the information about the i-th friend. The 2i-th line contains three integers xi, ki and mi (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 contains mi distinct positive integers — the numbers of problems that the i-th friend can solve. The problems are numbered from 1 to m.

Output

Print the minimum amount of money Gena needs to spend to solve all the problems. Or print -1, if this cannot be achieved

input

Copy

2 2 1
100 1 1
2
100 2 1
1

output

Copy

202

input

Copy

3 2 5
100 1 1
1
100 1 1
2
200 1 2
1 2

output

Copy

205

input

Copy

1 2 1
1 1 1
1

output

Copy

-1

http://my-zhang.github.io/blog/2014/04/20/dynamic-programming-with-bitmask/

typedef long long ll; struct Friend { int id; // friend id. ll cost; // the cost of solving problems. ll monitor; // the necessary num of monitors. int solves; // the bitmask of solvable problems. }; bool cmp(Friend a, Friend b) { return a.monitor < b.monitor; } Friend friends[N]; ll dp[1<<M]; int main() { int n, m; // number of friends and problems. ll b; // cost of monitor. cin >> n >> m >> b; for(int i = 0; i < (1<<m); i++) { dp[i] = INF; // initially marked as impossible. } dp[0] = 0; /* input processing. */ for(int i = 0; i < n; i++) { ll cost, monitor, num; int solves = 0; cin >> cost >> monitor >> num; for(int j = 0; j < num; j++) { int qid; cin >> qid; solves |= (1 << (qid-1)); } friends[i] = (Friend){i+1, cost, monitor, solves}; } // start with the friend with minimum monitor number. sort(friends, friends+n, cmp); ll min_cost = INF; for(int fid = 0; fid < n; fid++) { Friend f = friends[fid]; for(int i = 0; i < (1<<m); i++) { if(dp[i] == INF) { continue; } if(dp[i | f.solves] == INF) { dp[i | f.solves] = dp[i] + f.cost; } else { dp[i | f.solves] = min(dp[i | f.solves], dp[i] + f.cost); } } if(dp[(1<<m) - 1] != INF) { if(min_cost == INF) { min_cost = (dp[(1<<m) - 1] + f.monitor * b); } else { min_cost = min(min_cost, dp[(1<<m) - 1] + f.monitor * b); } } } cout << min_cost << endl; }

1. 题意：你要让n个朋友做完m道题，每个人能做掉特定某些题目，有一个花费x和需要的monitor（班长）个数，每个monitor（监视器）需要一定花费，但是monitor（显示屏）可以给所有朋友公用。求做完所有题的最小花费。（e.i. m很小）
2. 思路：m很小，所以压缩m的所有状态。f[state]表示做了state状态所花费的最小费用（不买monitor）。然而monitor还是需要管的，所以把所有朋友按monitor数量升序排序，这样每次用一个朋友更新状态时他自己必然是需要monitor最多的，那就拿他自己的monitor数量更新就好了。
3. 实现：排序+状压DP
4. 曾经的错误思路：monitor数量降序排列，然后f[state]表示加上monitor之后的最小价值，g[state]表示对应的f[state]状态去掉monitor花费后的价格。因为降序，所以所有f[nxt]都是由已经拥有比他大的monitor数量的状态转移过来，所以只要再加上买朋友的花费就好了。然而这样的思路不能保证记录的f[]最优，因为有monitor的影响，如果有monitor较少但f值较大的，他不会被更新，这是错误的。

我们发现由于所需要的监视器数量不同，所以我们要将监视器数量从小到大

排序，然后状压DP，因为后面所需监视器超过前面，所以我们不必再考虑监

视器够不够

https://www.cnblogs.com/hehe54321/p/cf-417d.html

先将小伙伴按需要的监视器数量排序。然后ans[i][j]表示前i个小伙伴完成j集合内题目所需最少钱。那么按顺序枚举小伙伴，用ans[i-1][j]更新ans[i][j]和ans[i][j | 第i个小伙伴能完成题目的集合]（更新后一种时答案要加上第i个小伙伴的费用）。

由于小伙伴已经按监视器数量排序了，对于每个枚举出的小伙伴i，可以试着将其作为最后一个要求助的小伙伴，那么此时监视器上花的钱就是这个小伙伴所需监视器数量*每个的费用，求助小伙伴费用就是ans[i][所有题目的集合]，此时总费用就是这两者的总和。最终答案就是最小的枚举得到的总费用。

可以开滚动数组优化空间。

https://xwk.iteye.com/blog/2130990

解题思路：dp[i]，i为一个二进制数，表示完成这些题目的最小代价，但是这里要注意，因为有个监视器的数量，一般情况下要开一个二维的状态，但是2^20次方有一百万，再多一维的数组会超内存，所以我的做法是将每个小伙伴按照监视器的数量从小到达排序，慢慢向上加。

1. typedef long long ll;  
2. const int N = (1<<20)+5;  
3. const int M = 105;  
4. const ll INF = 0x3f3f3f3f3f3f3f3f;  
5.   
6. struct state {  
7.     int s;  
8.     ll k, val;  
9. }p[M];  
10. int n, m;  
11. ll b, dp[N];  
12.   
13. bool cmp (const state& a, const state& b) {  
14.     return a.k < b.k;  
15. }  
16.   
17. void init () {  
18.     memset(dp, -1, sizeof(dp));  
19.   
20.     scanf("%d%d", &n, &m);  
21.     cin >> b;  
22.   
23.     int t, a;  
24.     for (int i = 0; i < n; i++) {  
25.         cin >> p[i].val >> p[i].k >> t;  
26.         p[i].s = 0;  
27.         for (int j = 0; j < t; j++) {  
28.             scanf("%d", &a);  
29.             p[i].s |= (1<<(a-1));  
30.         }  
31.     }  
32.     sort(p, p + n, cmp);  
33. }  
34.   
35. ll solve () {  
36.     dp[0] = 0;  
37.   
38.     int t = (1<<m)-1;  
39.     ll ans = INF;  
40.     for (int i = 0; i < n; i++) {  
41.   
42.         for (int j = 0; j <= t; j++) {  
43.             if (dp[j] == -1) continue;  
44.   
45.             int u = p[i].s | j;  
46.   
47.             if (dp[u] == -1)  
48.                 dp[u] = p[i].val + dp[j];  
49.             else   
50.                 dp[u] = min(dp[u], p[i].val + dp[j]);  
51.         }  
52.   
53.         if (dp[t] != -1)  
54.             ans = min(ans, dp[t] + p[i].k * b);  
55.     }  
56.   
57.     return ans == INF ? -1 : ans;  
58. }