题解：AT_abc404_d [ABC404D] Goin' to the Zoo

题意

AtCoder 国有

n

个动物园，第

i

个动物园门票为

C_i

元,一个人要去动物园看动物，他喜欢

M

种动物，第

i

种动物在

K_i

个动物园里有，这

K_i

个动物园分别是

A_{i,1},\dots,\ A_{i,K_i}

，他要求每种他喜欢的动物都要看两遍，问他最少要花多少钱。

思路

因为每个动物只看两遍，所以一个动物园最多去两次，我们就可以用三进制枚举每个动物园去几次就行了。时间复杂度

O(3^n)

。

代码

CPP

#include <bits/stdc++.h>
using namespace std;
long long n,m,a[1001][1001],b[1001],c[1001],d[1001],e[1001],ans=1e18;
void dfs(long long i,long long x){
	if(x>=ans){
		return;
	}
	if(i==n+1){
		for(long long j=1;j<=m;j++){
			for(long long k=1;k<=c[j];k++){
				e[j]+=d[a[j][k]];
			}
		}
		bool ok=1;
		for(long long j=1;j<=m;j++){
			if(e[j]<2){
				ok=0;
			}
			e[j]=0;
		}
		if(ok){
			ans=x;
		}
		return;
	}
	d[i]=0;
	dfs(i+1,x);
	d[i]=1;
	dfs(i+1,x+b[i]);
	d[i]=2;
	dfs(i+1,x+b[i]*2);
}
int main(){
	scanf("%lld%lld",&n,&m);
	for(long long i=1;i<=n;i++){
		scanf("%lld",&b[i]);
		b[i+n]=b[i];
	}
	for(long long i=1;i<=m;i++){
		scanf("%lld",&c[i]);
		c[i+n]=c[i];
		for(long long j=1;j<=c[i];j++){
			scanf("%lld",&a[i][j]);
			a[i+n][j]=a[i][j];
		}
	}
	dfs(1,0);
	printf("%lld",ans);
}

题解：AT_abc404_d [ABC404D] Goin' to the Zoo

文章操作

题意

思路

代码

相关推荐

评论

题解：AT_abc404_d [ABC404D] Goin' to the Zoo