题目大意

给出 $N$ 个箱子和 $M$ 把钥匙，每把钥匙能开 $b_i$ 个固定编号箱子，且价值为 $a_i$，求打开全部门的费用的最小值。如果不能打开所有门，则输出 $-1$。

思路

因为 $1 \leq N \leq 12$，考虑状态压缩，设 $dp_i$ 为在 $i$ 状态下的费用的最小值，则转移方程为 $dp_i=\min(dp_i,dp_j+dp_{i \oplus j})$。这种转移显然是有问题的，每个给出的状态不一定相互对应，所以我考虑到一种 $down_i$ 操作：

• 对于给出状态 $i$，枚举状态 $0 \leq j \leq i$
• 如果 $i \mid j=i$，$dp_j=\min(dp_j,dp_i)$

$down_i$ 解释：当状态 $j$ 开的箱子数量不大于状态 $i$，且对于状态 $i$ 未打开的每个箱子状态 $j$ 也未打开，这时花 $dp_i$ 的代价也可以开状态 $j$ 的箱子。

至于判无解，可以统计钥匙的种类数，如果种类数小于箱子数，即为无解。

具体细节请参考代码。

Code

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,m,dp[5005],c[5005],s;
bool k[5005];
signed main(){
	cin>>n>>m;
	c[1]=1;
	for(int i=2;i<=n;i++) c[i]=c[i-1]*2;//预处理2的次方 
	memset(dp,0x3f,sizeof dp); //初始化 
	for(int i=1;i<=m;i++){
		int a,b,w=0;
		cin>>a>>b;
		for(int j=1;j<=b;j++){
			int x;
			cin>>x;
			w+=c[x];
			if(!k[x]) k[x]=1,s++;//统计钥匙种类 
		}
		for(int j=0;j<=w;j++)//down操作 
			if((w|j)==w) dp[j]=min(dp[j],a);
	}
	if(s<n){//判无解 
		cout<<-1;
		return 0;
	}
	for(int i=0;i<(1<<n);i++)
		for(int j=0;j<=i;j++)
			dp[i]=min(dp[i],dp[i^j]+dp[j]);//状态转移 
	cout<<dp[(1<<n)-1]<<endl;
	return 0;
}