AT_abc404_d [ABC404D] Goin#39； to the Zoo 题解

题目传送门

题目大意

AtCoder 国家有 $N$ 个动物园，编号为 $1$ 至 $N$。动物园 $i$ 的门票是 $C_i$ 日元。

铃木先生喜欢 $M$ 种动物，动物 $1,\dots ,M$。
动物园 $K_i$，即动物园 $A_{i,1},\dots ,A_{i,K_i}$ 可以看到动物 $i$。

求观看所有 $M$ 种动物每种至少两次所需的最低门票总额。
如果你多次游览同一个动物园，那么那里的动物就被视为每次游览都能看到一次。

解题思路

注意到 $1\le n\le 10$，所以考虑直接爆搜。

我们枚举第 $i$ 种动物园游玩 $0,1,2$ 次，然后最后统计每种动物是否都看到了 $2$ 次及以上，与答案取一个最小值即可。

CODE：

#include <bits/stdc++.h>
using namespace std;
#define int long long
int n, m, c[20], a[110][10], k[110], cnt[110];
int ans = 1e18;
inline void dfs(int step, int x) {if (step == n + 1) {for (int i = 1; i <= m; i++) {int res = 0;for (int j = 1; j <= k[i]; j++)res += cnt[a[i][j]];if (res < 2) {return;}}ans = min(ans, x);return;}for (int t = 0; t <= 2; t++) {int nc = x + t * c[step];if (nc >= ans) {return;}cnt[step] = t;dfs(step + 1, nc);cnt[step] = 0;}
}
signed main() {ios::sync_with_stdio(false);ios_base::sync_with_stdio(false);cin.tie(0), cout.tie(0);cin >> n >> m;for (int i = 1; i <= n; i++) {cin >> c[i];}for (int i = 1; i <= m; i++) {cin >> k[i];for (int j = 1; j <= k[i]; j++) {cin >> a[i][j];}}dfs(1, 0);cout << ans;return 0;
}