CF1519F - Chests and Keys

题目大意

给定$n$个宝箱，$m$种锁和对应的钥匙

每个箱子有$a_i$块钱，每种钥匙$b_i$块，给箱子$i$装上$j$这种锁需要$c_{i,j}$的代价

一个箱子可以装多把锁

求最小的代价，使得无论怎么买钥匙取开箱子都无法赚钱



$n,m\leq 6,a_i,b_i\leq 4$

？？？？？？

《关于Codeforce 3200 是朴素搜索一事》

复杂度上限？大概$2^{41}++$

-> 873ms

再把-1判掉

->31ms

CodeForces Submission

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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=a,i##end=b;i<=i##end;++i)
#define drep(i,a,b) for(int i=a,i##end=b;i>=i##end;--i)

const int N=10,P=998244353;

int n,m;
int a[N],b[N],c[N][N];
int A[1<<6],B[1<<6],s[N][1<<6],bin[1<<6];
int C[1<<6];

int st[N];
int ans=1e9;
void dfs(int p,int s){
	if(s>=ans) return;
	if(p==n) { ans=s; return; }
	rep(S,0,(1<<m)-1) {
		int fl=1;
		if(s+::s[p][S]>=ans) continue;
		st[p]=S;
		drep(T,(1<<(p+1))-1,1<<p) {
			C[T]=C[T^(1<<p)]|st[p];
			if(A[T]>B[C[T]]) {
				fl=0;
				break;
			}
		}
		if(fl) dfs(p+1,s+::s[p][S]);
	}
}

int main(){
	scanf("%d%d",&n,&m);
	rep(i,0,max(n,m)-1) bin[1<<i]=i;
	rep(i,0,n-1) scanf("%d",a+i);
	rep(i,0,m-1) scanf("%d",b+i);
	rep(i,0,n-1) rep(j,0,m-1) scanf("%d",c[i]+j);
	rep(i,0,n-1) rep(j,i+1,n-1) if(a[j]>a[i]) swap(a[i],a[j]),swap(c[i],c[j]);
	rep(S,1,(1<<n)-1) A[S]=A[S&(S-1)]+a[bin[S&-S]];
	rep(S,1,(1<<m)-1) B[S]=B[S&(S-1)]+b[bin[S&-S]];
	rep(i,0,n-1) rep(S,1,(1<<m)-1) s[i][S]=s[i][S&(S-1)]+c[i][bin[S&-S]];
	int s=0;
	rep(i,0,n-1) s+=a[i];
	rep(i,0,m-1) s-=b[i];
	if(s>0) return puts("-1"),0;
	dfs(0,0);
	printf("%d\n",ans==1e9?-1:ans);
}