ABC-404-D - Goin' to the Zoo · znzryb

## 思路讲解

jiangly的代码利用了状压dp的思想，我汲取一下思想，来写一波

## AC代码

[https://atcoder.jp/contests/abc404/submissions/65496213](https://atcoder.jp/contests/abc404/submissions/65496213)



::: 源代码

```cpp
#include <bits/stdc++.h>
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define fi first
#define se second
#define pb push_back
#define SZ(a) ((int) a.size())
#define FOR(i, a, b) for (int i = (a); i <= (b); ++i)
#define ROF(i, a, b) for (int i = (a); i >= (b); --i)

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef __int128 i128;
typedef pair<ll,ll> pll;
typedef array<ll,3> arr;
typedef double DB;
typedef pair<DB,DB> pdd;
typedef pair<ll,bool> plb;
constexpr ll MAXN=static_cast<ll>(1e3)+10,INF=static_cast<ll>(1e18)+3;
constexpr ll mod=static_cast<ll>(1e9)+7;
constexpr double eps=1e-8;

ll N,M,K,T,Cost[MAXN];
vector<ll> g[MAXN];
ll pw[20];

inline void solve(){
	cin>>N>>M;	// M个动物，N个动物园
	FOR(i,1,N){
		cin>>Cost[i];
	}
	FOR(i,1,M){
		cin>>K;
		FOR(j,1,K){
			ll u;
			cin>>u;
			g[u].pb(i);
		}
	}
// #ifdef LOCAL
    // FOR(i,1,N){
    	// cerr<<"zoo:"<<i<<" animial:";
    	// FOR(j,0,SZ(g[i])-1){
    		// cerr<<g[i][j]<<" ";
    	// }
    	// cerr<<"\n";
    // }
// #endif
	pw[0]=1;
	FOR(i,1,N){
		pw[i]=pw[i-1]*3;
	}
	ll ans=INF;
	FOR(i,0,pw[N]){
		ll opi=i,idx=1,ct=0;
		vector<ll> Cnt(M,0);
// #ifdef LOCAL
    // cerr <<"status:"<<i <<" rem:";
// #endif
		while(opi){
			ll rem=opi%3;
			if(rem!=0){
				ct+=Cost[idx]*rem;
				FOR(j,0,SZ(g[idx])-1){
					Cnt[g[idx][j]-1]+=rem;
				}
			}
			++idx;
// #ifdef LOCAL
    // cerr << rem;
// #endif
			opi/=3;
		}
// #ifdef LOCAL
    // cerr  << '\n';
// #endif
// #ifdef LOCAL
	// cerr<<"Cnt:";
	// FOR(i,0,M-1){
		// cerr<<Cnt[i]<<" ";
	// }
	// cerr<<"\n";
// #endif
		if(*min_element(all(Cnt))>=2){
			ans=min(ct,ans);
// #ifdef LOCAL
    // cerr << "OK" << '\n';
// #endif
		}
// #ifdef LOCAL
    // cerr<<"status:"<<i << "Cost:"<<ct << '\n';
// #endif
	}
	cout<<ans<<"\n";
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);
	// cin>>T;
	// while(T--){
		// solve();
	// }
	solve();
	return 0;
}
/*

*/	
```


:::


## 心路历程（WA，TLE，MLE……）