Untitled

mail@pastecode.io avatar
unknown
plain_text
20 days ago
2.3 kB
2
Indexable
Never
#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
using namespace std;

int nTestcase, N, M, L, price, Min;
int market[21], sale[31][25], need[21], visited[21];

bool check() {
	for (int i = 0; i < L; i++) {
		if (visited[i] == 0) return false;
	}
	return true;
}

bool solution(int k) {
	for (int i = 0; i < sale[k][1]; i++) {
		for (int j = 0; j < L; j++) {
			if (need[j] == sale[k][i + 2] && visited[j] == 0)
				return true;
		}
	}
	return false;
}

void buy(int k) {
	for (int i = 0; i < sale[k][1]; i++) {
		for (int j = 0; j < L; j++) {
			if (need[j] == sale[k][i + 2])
				visited[j]++;
		}
	}
}

void unbuy(int k) {
	for (int i = 0; i < sale[k][1]; i++) {
		for (int j = 0; j < L; j++) {
			if (need[j] == sale[k][i + 2])
				visited[j]--;
		}
	}
}

void backtrack(int k) {
	if (price >= Min)
		return;

	if (check()) {
		Min = Min > price ? price : Min;
		return;
	}
	else {
		for (int i = 0; i < L; i++) {
			if (visited[i] == 0)
				price += market[need[i] - 1];
		}
		Min = Min > price ? price : Min;
		for (int i = 0; i < L; i++) {
			if (visited[i] == 0)
				price -= market[need[i] - 1];
		}
	}
	if (k == M) {
		/*if (check()) {
			Min = Min > price ? price : Min;
		}
		else {
			for (int i = 0; i < L; i++) {
				if (visited[i] == 0)
					price += market[need[i] - 1];
			}
			Min = Min > price ? price : Min;
			for (int i = 0; i < L; i++) {
				if (visited[i] == 0)
					price -= market[need[i] - 1];
			}
		}*/
		return;
	}
	for (int i = 0; i < 2; i++) {
		if (i == 0 && solution(k)) {
			price += sale[k][0];
			buy(k);
			backtrack(k + 1);
			unbuy(k);
			price -= sale[k][0];
		}
		else
		{
			backtrack(k + 1);
		}
	}
}

int main() {
	freopen("input.txt", "r", stdin);
	cin >> nTestcase;
	for (int testcase = 1; testcase <= nTestcase; testcase++) {
		cin >> N;
		for (int i = 0; i < N; i++) {
			cin >> market[i];
		}
		cin >> M;
		for (int i = 0; i < M; i++) {
			cin >> sale[i][0] >> sale[i][1];
			for (int j = 2; j < sale[i][1] + 2; j++) {
				cin >> sale[i][j];
			}
		}
		cin >> L;
		for (int i = 0; i < L; i++) {
			cin >> need[i];
			visited[i] = 0;
		}
		Min = 1000000000;
		price = 0;
		backtrack(0);
		cout << "#" << testcase << " " << Min << endl;
	}
	return 0;
}