nangcapmaytinhquocdepzai
quoc14
c_cpp
a month ago
1.7 kB
1
Indexable
Never
caidat
#include <iostream> using namespace std; int n; int a[200]; int m; int dem[200]; struct docanmua { int num_buy; int L[100]; }; struct goikhuyenmai { int num_sale; int gia; int M[100]; }; docanmua x; goikhuyenmai y[100]; int damua[100]; int minGia; bool checkFull() { for (int i = 1; i <= x.num_buy; i++) { if (dem[x.L[i]] == 0) return false; } return true; } void update(int k, int x) { for (int i = 1; i <= y[k].num_sale; i++) { dem[y[k].M[i]] += x; } } // k goi khuyen mai void backtrack(int k, int curPrice) { if (curPrice > minGia) return; if (checkFull()) { if (curPrice < minGia) minGia = curPrice; return; } if (k == m + 1) { for (int i = 1; i <= x.num_buy; i++) { if (dem[x.L[i]] == 0) { curPrice += a[x.L[i]]; } } if (curPrice < minGia) minGia = curPrice; return; } for (int i = 0; i < 2; i++) { // mua if (i == 1) { update(k, 1); backtrack(k + 1, curPrice + y[k].gia); update(k, -1); } // k mua else { backtrack(k + 1, curPrice); } } } void solve(int testcase) { cin >> n; for (int i = 1; i <= n; i++) { cin >> a[i]; } cin >> m; for (int i = 1; i <= m; i++) { cin >> y[i].gia; cin >> y[i].num_sale; for (int j = 1; j <= y[i].num_sale; j++) { cin >> y[i].M[j]; } } cin >> x.num_buy; for (int i = 1; i <= x.num_buy; i++) { cin >> x.L[i]; } minGia = 1e8; backtrack(1, 0); cout << "#" << testcase << " " << minGia << endl; } int main() { int t; cin >> t; for (int i = 1; i <= t; i++) { solve(i); } return 0; }
Leave a Comment