[ABC142] E.Get Everything

发表于 | 更新于 | 分类于 ， ，
本文字数： 6.2k

链接

\(\text{ABC142 E - Get Everything}\)

题意

  这里有\(n\)个锁着的箱子，你需要购买一些钥匙来打开这\(n\)个箱子，这里有\(m\)钥匙，第\(i\)个钥匙的花费为\(a_i\)，它能打开\(n\)个箱子中的\(b_i\)个，分别是\(c_{i1}、c_{i2}\dots c_{i{b_{n}}}\)，现在你需要从这\(m\)个钥匙中选出若干个钥匙来打开这\(n\)个箱子，使得花费最小。

  输入格式：第一行\(n、m\)，之后\(2*m\)行，每连续两行的第一行，\(a_i、b_i\)，之后一行\(b_i\)个数，代表这个钥匙可以打开的箱子的编号。

  输出格式：输出一行最小花费.

  数据范围：\(1\leq n\leq 12,1\leq m\leq 10^3,1\leq a_{i}\leq 10^5,1\leq b_i\leq n,1\leq c_{i1}<c_{i2}<\dots <c_{ib_{i}}\leq n\).

分析

  第一印象这是个\(dp\)，注意到\(n\)最大为\(12\)，并结合题意可知，需要使用状压\(dp\)；

  二进制压缩保存每个钥匙能开的那些宝箱的状态，\(1\)表示箱子可以被开，\(0\)表示箱子不能被打开，\(f[i]\)表示打开箱子的状态为\(i\)时，所需要的最小花费，枚举箱子的状态\(i\)和第\(j\)枚钥匙，进行状态转移：

\[f[i|state[j]]=\min(f[i|state[j]],f[i]+cost[j])\]

  初始状态\(f[0]\)为\(0\)，其他为\(\infty\)，目标为\(f[(1<<n)-1]\).

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <bits/stdc++.h>
 
using namespace std;
 
struct node{
	int cost, state;
}p[1005];
 
int n, m, f[1 << 14];
int main() {
	cin >> n >> m;
  	memset(f, 0x3f3f3f3f, sizeof(f));
  	f[0] = 0;
  	for (int i = 1; i <= m; i++){
    	cin >> p[i].cost;
    	int sum = 0, t, x;
      	cin >> t;
      	while (t--) {
        	cin >> x;
          	sum += (1 << (x - 1));
        }
    	p[i].state = sum;
      	f[sum] = p[i].cost;
    }
  	for (int i = 0; i < 1 << n; i++)
      	for (int j = 1; j <= m; j++) {
        	f[i | p[j].state] = min(f[i | p[j].state], f[i] + p[j].cost);
        }
  	if (f[(1 << n) - 1] == 0x3f3f3f3f)cout << -1 << endl;
  	else cout << f[(1 << n) - 1] << endl;
}