nangcapmaytinhc2
duyvan
plain_text
19 days ago
2.4 kB
2
Indexable
Never
#include<iostream> using namespace std; //int LinhKien[21]; // mang luu gia linh kien int SL; // so luong linh kien chinh int SLuudai; // so luong uu dai int UuDai[60][60]; int Slcanmua; int Mua[40]; //int visit[20]= {0}; // check du so luong can mua //int countt; //int Vitri[60]; bool visit[60]; int Hang[60][60]; int A[60] = {}; int minx; void xuat(){ int ans = 0; for(int i = 1; i <= Slcanmua; i++){ //cout<<A[i]<<" "; if(visit[A[i]-1] == -1){ ans+=UuDai[A[i]-1][0]; } visit[A[i]-1] = 1; } if(minx > ans) minx = ans; //cout<<ans<<endl; } int ans; void sinh(int idx, int dodai, int sum){ if(sum > ans) return; if(idx == Slcanmua+1){ ans = min(ans, sum); return; } for(int i = 1; i < 1 + dodai; i++){ A[idx] = Hang[Mua[idx-1]][i]; if(visit[A[idx]] == false){ visit[A[idx]] = true; sinh(idx+1, Hang[Mua[idx]][0], sum + UuDai[A[idx]-1][0]); visit[Hang[Mua[idx-1]][i]] = false; } else { sinh(idx+1, Hang[Mua[idx]][0], sum); } } } int main(){ //freopen("input.txt", "r", stdin); //freopen("outputt.txt", "w", stdout); int T; cin>>T; for(int tc = 0; tc < T; tc++){ cin>>SL; ans = 9999; for(int i = 0; i < 60;i++){ visit[i] = 0; } for(int i = 0; i < 60; i++){ for(int j = 0; j < 60; j++) { UuDai[i][j] = 0; Hang[i][j] = 0; } } for(int i = 0; i < SL; i++) { cin>>UuDai[i][0]; UuDai[i][3] = i+1; UuDai[i][1] = 1; } cin>>SLuudai; for(int i = 0; i < SLuudai; i++){ cin>>UuDai[i+SL][0]>>UuDai[i+SL][1]; for(int j = 0; j < UuDai[i+SL][1]; j++){ cin>>UuDai[i+SL][j+3]; } } cin>>Slcanmua; //countt = 0; for(int i = 0; i < Slcanmua; i++) cin>>Mua[i]; // Bai lam //UuDai: UuDai[0]: Gia, UuDai[1]: SL trong hang, UuDai[2] ton tai linh kien can mua // UuDai[3,4,5...] ma linh kien for(int k = 0; k < Slcanmua; k++) { int count = 1; int countt = 0; for(int i = 0; i < SLuudai+SL; i++) // check toan bo hang { for(int j = 0; j < UuDai[i][1]; j++) // check tren tung hang { if(UuDai[i][j+3] == Mua[k]) { Hang[Mua[k]][count] = i+1; count++; //UuDai[i][2] = UuDai[i][j+3]; countt++; } } } Hang[Mua[k]][0] = countt; } int cnt = 0; sinh(1, Hang[Mua[0]][0], 0); cout<<"#"<<tc+1<<" "<<ans<<endl; } return 0; }
Leave a Comment