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

laiyouming · 2025-05-08 08:51:38 · 题解

题意

AtCoder 国有 n 个动物园，第 i 个动物园门票为 C_i 元,一个人要去动物园看动物，他喜欢 M 种动物，第 i 种动物在 K_i 个动物园里有，这 K_i 个动物园分别是 A_{i,1},\dots,\ A_{i,K_i} ，他要求每种他喜欢的动物都要看两遍，问他最少要花多少钱。

思路

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

代码

#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);
}