Untitled
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...