题目大意

有

n

个动物园，参观动物园

i

需要

c_i

元，而在

k_i

个动物园中，可以看到动物

i

。问将

1\sim m

的动物看至少两遍最小要花费多少元。

解法

从数据范围中，我们可以发现直接使用 DFS 也不会超时，所以我们只需要在 DFS 中遍历每个动物园取

0,1,2

次即可（因为动物园的动物至少有一个，取二次之后一定会满足条件）。

代码

CPP

#include <bits/stdc++.h>
#define int long long
const int N = 15;
const int M = 105;
const int Mod = 1e9 + 7;
using namespace std;
int n, m;
int c[N];
vector<int> vec[N];
int vis[M];
int ans = 1e18;
void dfs(int x, int y)
{
    if (x == n + 1)
    {
        for (int i = 1; i <= m; i++)
        {
            if (vis[i] < 2)
            {
                return;
            }
        }
        ans = min(ans, y);
        return;
    }
    dfs(x + 1, y);
    for (int i : vec[x])
    {
        vis[i]++;
    }
    dfs(x + 1, y + c[x]);
    for (int i : vec[x])
    {
        vis[i]++;
    }
    dfs(x + 1, y + c[x] * 2);
    for (int i : vec[x])
    {
        vis[i] -= 2;
    }
}
signed main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
    {
        cin >> c[i];
    }
    for (int i = 1; i <= m; i++)
    {
        int k;
        cin >> k;
        while (k--)
        {
            int x;
            cin >> x;
            vec[x].push_back(i);
        }
    }
    dfs(1, 0);
    cout << ans;
    return 0;
}

提交记录

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

文章操作

题目大意

解法

代码

相关推荐

评论

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