Untitled
unknown
plain_text
2 years ago
1.7 kB
3
Indexable
#include <iostream> using namespace std; int N, M, K, skyMarket[21], combo[30][21], need[21], buy[21], minPrice; bool hasNeed; void select(int k) { hasNeed = false; for (int i = 2; i < combo[k][1] + 2; i++) { if (buy[combo[k][i]] < 1) hasNeed = true; buy[combo[k][i]]++; } } void deselect(int k) { for (int i = 2; i < combo[k][1] + 2; i++) { buy[combo[k][i]]--; } } bool check() { for (int i = 0; i < K; i++) { if (buy[need[i]] == 0) return false; } return true; } void backtrack(int k, int sum) { if (sum >= minPrice) return; if (check()) { if (sum < minPrice) minPrice = sum; return; } if (!hasNeed) { hasNeed = true; return; } if (k == M) { int price = sum; for (int i = 0; i < K; i++) { if (buy[need[i]] == 0) { price += skyMarket[need[i]]; } } if (price < minPrice) minPrice = price; return; } for (int i = 0; i < 2; i++) { if (i == 0) { backtrack(k + 1, sum); } else { select(k); backtrack(k + 1, sum + combo[k][0]); deselect(k); } } } int main() { freopen("input.txt", "r", stdin); int T; cin >> T; for (int tc = 1; tc <= T; tc++) { cin >> N; for (int i = 1; i <= N; i++) { cin >> skyMarket[i]; buy[i] = 0; } cin >> M; for (int i = 0; i < M; i++) { cin >> combo[i][0] >> combo[i][1]; for (int j = 2; j < 2 + combo[i][1]; j++) { cin >> combo[i][j]; } } cin >> K; minPrice = 0; for (int i = 0; i < K; i++) { cin >> need[i]; minPrice += skyMarket[need[i]]; } hasNeed = true; backtrack(0, 0); cout << "#" << tc << " " << minPrice <<endl; } return 0; }
Editor is loading...