Untitled
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; }