Untitled

mail@pastecode.io avatar
unknown
plain_text
a year ago
2.1 kB
3
Indexable
Never
#include <iostream>
using namespace std;

int N; 
int packages;
int prices[35]; 
int p[35][35]; 
int a[35]; // need
int needs; 
int bought[35]; // visit
int total;

void reset(){
	for(int i = 0; i < 35; i++){
		prices[i] = 0;
		a[i] = 0;
		bought[i] = 0;
		for(int j = 0; j < 35; j++){
			p[i][j] = 0;
		}
	}
}

int buy(int k){
	int cnt = 0;
	for(int j = 1; j <= N; j++){
		if(p[k][j] == 1 && a[j] == 1 && bought[j] == 0) {
			cnt++;
		}
	}

	return cnt;
}

int calPrice(int k){
	int sum = 0;
	for(int j = 1; j <= N; j++){
		if(p[k][j] == 1 && a[j] == 1) {
			sum += prices[j];
		}
	}

	return sum;
}

void mark(int k){
	for(int j = 1; j <= N; j++){
		if(a[j] == 1 && p[k][j] == 1) {
			bought[j]++;
		}
	}
}

void unmark(int k){
	for(int j = 1; j <= N; j++){
		if(a[j] == 1 && p[k][j] == 1 && bought[j] != 0) {
			bought[j]--;
		}
	}
}

void kt(){
	for(int i = 1; i <= N; i++){
		cout << bought[i] << " ";
	}
	cout << endl;
}

void Try(int sum, int cnt, int t){
	if(sum > total) return;

	if(cnt == needs){ 
		if(sum < total) total = sum;
		return;
	}

	if(t == packages + 1 && cnt < needs){ 
		for(int k = 1; k <= N; k++){
			if(bought[k] == 0 && a[k] == 1){
				sum += prices[k];
			}
		}
		if(sum < total) total = sum;
		return;
	}

	int c = buy(t);
	if(c > 0){ 
		mark(t);
		Try(sum + p[t][N + 1], cnt + c, t+1);
		unmark(t);
		Try(sum, cnt, t+1);
	}else {
		Try(sum, cnt, t+1);
	}
}

int main(){
	// freopen("input.txt", "r", stdin);
	int T; cin >> T;

	for(int tc = 1; tc <= T; tc++){
		cin >> N;
		reset();

		for(int i = 1; i <= N; i++){
			cin >> prices[i];
		}

		cin >> packages;
		for(int i = 1; i <= packages; i++){
			int price, cnt;
			cin >> price >> cnt;
			for(int j = 1; j <= cnt; j++){
				int x; cin >> x;
				p[i][x] = 1;
			}
			p[i][N + 1] = price;
			p[i][N + 2] = cnt;
		}

		cin >> needs;
		for(int i = 1; i <= needs; i++){
			int x; cin >> x;
			a[x] = 1;
            total += prices[x];
		}

		Try(0, 0, 1);

		cout << "#" << tc << " " << total << endl;
	}

	return 0;
}