hugo_venhac
duyvan
plain_text
a year ago
2.9 kB
17
Indexable
//hugo_venha_oanhnhau #include<iostream> #define endl '\n' using namespace std; int N, ans; int creeps[7][3]; int price_gate[7]; void copy_arr(int arr1[7][3], int arr2[7][3]) { for(int i = 0; i < N; ++i) for(int j = 0; j < 3; ++j) arr2[i][j] = arr1[i][j]; } void backtrack(int x, int crs, int score) { if(score >= ans) return; if(x == N) { if(score < ans) ans = min(ans, score); return; } for(int i = 1; i <= 3; ++i) { if(i == 1) backtrack(x + 1, crs, score + price_gate[x]); //Neu qua cong do, nap tien vao cong -> score tang, crs khong doi, x them 1 cong if(i == 2) { creeps[x][1] = creeps[x][0]; //Nap linh vao quan minh backtrack(x + 1, crs + creeps[x][0], score + price_gate[x]*2); //Neu mua linh, score cong them gap 2, linh cong do them, tong crs them linh creeps[x][1] = 0; //Quay lui, creeps cua cong do ve lai 0 } if(i == 3 && crs >= creeps[x][0]) { int copy_crs[7][3]; copy_arr(creeps, copy_crs); //copy mang creeps truoc khi backtrack de ty quay lui int enemy = creeps[x][0]; //Dat bien so linh quan dich = linh cong do for(int j = 0; j < N; ++j) //Buoc 1: Cho moi tk quan cong do len 1 lan danh if(creeps[j][1] > 0) creeps[j][2]++; //So lan danh cua cong do tang 1 lan for(int j = 0; j < N; ++j) //Buoc 2: Scan linh de danh { if(creeps[j][1] > 0) //Neu cong do minh co mua linh { if(creeps[j][1] > enemy) //Neu so quan lon hon dich -> linh giam theo so luong dich, dich = 0 { creeps[j][1] -= enemy; enemy = 0; } if(creeps[j][1] <= enemy) //Neu so quan nho hon hoac bang dich -> linh, so lan danh = 0, dich giam theo so luong quan { enemy -= creeps[j][1]; creeps[j][2] = 0; creeps[j][1] = 0; } if(enemy == 0) break; //Neu so linh dich da het, break khoi tim quan dong minh nx } } for(int j = 0; j < N; ++j) //Buoc 3: Kiem tra xem co cong nao danh 3 lan chua, neu danh 3 lan -> cho giai tan if(creeps[j][2] == 3) { creeps[j][2] = 0; creeps[j][1] = 0; } crs = 0; //reset creeps de cong lai tong quan linh sau tran chien for(int j = 0; j < N; ++j) if(creeps[j][1] > 0) //Neu cong do con quan ta -> cong vao crs crs += creeps[j][1]; backtrack(x + 1, crs, score); copy_arr(copy_crs, creeps); crs = 0; //Sau backtrack, reset crs, copy lai mang arr cu, cong lai crs va quay lui tiep for(int j = 0; j < N; ++j) if(creeps[j][1] > 0) //Neu cong do con quan ta -> cong vao crs crs += creeps[j][1]; } } } int main() { ios::sync_with_stdio(false); freopen("inp.txt","r",stdin); freopen("out.txt","w",stdout); cin.tie(0); ans = 0; cin >> N; for(int i = 0; i < N; ++i) { cin >> creeps[i][0] >> price_gate[i]; ans += price_gate[i]; } backtrack(0,0,0); cout << ans << endl; return 0; }
Editor is loading...
Leave a Comment