Untitled

 avatar
unknown
plain_text
2 years ago
1.7 kB
6
Indexable
#include<iostream>
using namespace std;

int T, N, M, L, result;
int originPrize[25], packagePrize[35], packageCount[35], packageItem[35][25], needItem[25];
int cand[25][35], buyed[25];

void formatData() {
	result = 2000000000;
	for (int i = 1; i <= 20; i++) {
		buyed[i] = cand[i][0] = 0;
	}
}

void buy(int re, int count) {
	if (re > result) {
		return;
	}
	if (count == L + 1) {
		result = re < result ? re : result;
		return;
	}
	if (buyed[needItem[count]] > 0) {
		buy(re, count + 1);
	} else {
		buyed[needItem[count]]++;
		buy(re + originPrize[needItem[count]], count + 1);
		buyed[needItem[count]]--;

		for (int c = 1; c <= cand[needItem[count]][0]; c++) {
			for (int n = 1; n <= packageCount[cand[needItem[count]][c]]; n++) {
				buyed[packageItem[cand[needItem[count]][c]][n]]++;
			}
			buy(re + packagePrize[cand[needItem[count]][c]], count + 1);
			for (int n = 1; n <= packageCount[cand[needItem[count]][c]]; n++) {
				buyed[packageItem[cand[needItem[count]][c]][n]]--;
			}
		}
	}
}

int main() {
	ios::sync_with_stdio(false);
	//freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);

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

		for (int i = 1; i <= N; i++) {
			cin >> originPrize[i];
		}
		cin >> M;
		for (int i = 1; i <= M; i++) {
			cin >> packagePrize[i] >> packageCount[i];
			for (int j = 1; j <= packageCount[i]; j++) {
				cin >> packageItem[i][j];
				cand[packageItem[i][j]][0]++;
				cand[packageItem[i][j]][cand[packageItem[i][j]][0]] = i;
			}
		}
		cin >> L;
		for (int i = 1; i <= L; i++) {
			cin >> needItem[i];
		}

		buy(0, 1);
		cout << "#" << tc << " " << result << endl;
	}
}
Editor is loading...