Untitled
unknown
plain_text
2 years ago
2.6 kB
5
Indexable
#include<iostream> using namespace std; int N; // so linh kien chinh int RetailPrices[25]; // gia cho Troi int M; // so goi uu dai int ComboPrice[35]; // gia cua combo int ComboSize[35]; // so luong item cua combo int ComboList[35][25]; // cac goi uu dai int NumNeed; // so linh kien cam mua int NeedList[25]; // cac linh kien can mua int visitItems[25]; // item da mua int ans; int buyCombo(int c){ int cnt = 0; for (int i = 1; i <= ComboSize[c]; i++){ if (NeedList[i] == 1 && ComboList[c][i] == 1){ cnt++; } } return cnt; } void Try(int gia, int damua, int comboI){ if (gia > ans) return; if (damua == NumNeed) { if (gia < ans) ans = gia; return; } if (comboI == M+1 && damua < NumNeed){ for (int i = 1; i <= N; i++){ if (NeedList[i] == 1 && visitItems[i] == 0){ gia += RetailPrices[i]; } } if (gia < ans) ans = gia; return; } int cntComboI = buyCombo(comboI); if (cntComboI > 0){ // 1. mua combo for (int i = 1; i <= N; i++){ if (NeedList[i] == 1 && ComboList[comboI][i] == 1){ visitItems[i]++; } } Try(gia+ComboPrice[comboI],damua+cntComboI,comboI+1); // 2. khong mua combo for (int i = 1; i <= N; i++){ if (NeedList[i] == 1 && ComboList[comboI][i] == 1 && visitItems[i]!=0){ visitItems[i]--; } } Try(gia, damua, comboI+1); }else{ Try(gia, damua, comboI+1); } } void reset(){ ans = 0; for (int i = 1; i <= 25; i++){ RetailPrices[i] = 0; NeedList[i] = 0; visitItems[i] = 0; } for (int i = 1; i <= 35; i++){ ComboPrice[i] = 0; ComboSize[i] = 0; for (int j = 1; j <= 25; j++){ ComboList[i][j] = 0; } } } int main(){ freopen("input.txt", "r", stdin); int TC; cin >> TC; for (int tc = 1; tc <= TC; tc++){ reset(); cin >> N; for (int i = 1; i <= N; i++) { // gia tung item mua cho Troi cin >> RetailPrices[i]; } cin >> M; for (int i = 1; i <= M; i++){ // so item cua combo cin >> ComboPrice[i] >> ComboSize[i]; for (int j = 1; j <= ComboSize[i]; j++) { // item co trong combo = 1 int itemI; cin >> itemI; ComboList[i][itemI] = 1; } } for (int i = 1; i <= M; i++){ for (int j = 1; j <= N; j++) { cout << ComboList[i][j] << " "; } cout << endl; } cin >> NumNeed; for (int i = 1; i <= NumNeed; i++){ int need; cin >> need; // item can mua = 1 NeedList[need] = 1; ans += RetailPrices[need]; } Try(0,0,1); cout << "#" << tc << " " << ans << endl; } return 0; }
Editor is loading...