Untitled
unknown
plain_text
2 years ago
2.7 kB
6
Indexable
HUGO DANH NHAU Ông A cần đi qua 1 đoạn đường B. Trên đoạn đường đi qua có N cổng. Tại mỗi cổng có 1 số lượng binh sĩ và giá để đi qua cổng đó. Muốn đi qua mỗi cổng ông A có 3 cách lựa chọn. 1. Pass Trả số tiền quy định ở cổng đó để được đi qua 2. Hire Trả gấp đôi số tiền ở cổng đó để thuê số binh sĩ gộp vào đoàn quân của mình 3. battle Điều kiện để đánh nhau là số quân của ông A >= số lượng lính tại cổng đó. Có các lưu ý: + Ông A k được tính vào số lượng của quân + Mỗi người lính chỉ tham gia được vào tối đa 3 trận đánh. Sau 3 trận đánh nếu đi nhóm binh sĩ đó còn sống thì cũng giải tán. + Mỗi trận đánh thì tất cả số binh sĩ đều tham gia. + Đánh nhau chết theo tỉ lệ 1: 1. Ai tham gia trước sẽ bị chết trước Điều kiện input: số cổng <=20 -Số lính và chi phí đi qua >=2 và <=1000 Tìm chi phí nhỏ nhất để ông A có thể đi qua đoạn đường B VD: Có 7 cổng 1 2 3 4 5 6 7 Số binh sĩ 10 70 80 20 50 30 10 Chi phí 100 5 15 60 90 80 10 Có thể tính chi phí đi nhỏ nhất 1 2 3 4 5 6 7 Số binh sĩ 10 70 80 20 50 30 10 Chi phí 100 5 15 60 90 80 10 Chọn pp Pass Hire Hire Battle Battle Battle Pass Chi phí 100 110 140 150 Code: #include<iostream> using namespace std; int N; int cong[25][2]; //cot 0 la so linh canh o cong, cot 1 la chi phi int ans; void bt(int k, int fee, int l0, int l1, int l2){ if(fee > ans) return; if(k == N){ if(ans > fee){ ans = fee; } return; } for(int i=1; i<=3; i++){ if(i ==1 ){ //Case 1 : tra tien de qua cong bt(k+1, fee+cong[k][1], l0, l1,l2); } if(i == 2){ // Case 2:Tra tien de thue binh si bt(k+1, fee + 2*cong[k][1], l0+cong[k][0], l1, l2); } if(i==3){ // Case3: danh nhau, lai co 3 truong hop con o trong if((l0 + l1 +l2) >= cong[k][0]){ //check du quan de danh nhau // chi can luong quan l2 da du danh if(l2 >= cong[k][0]) bt(k+1, fee, 0, l0, l1); // luong quan l2 khong du danh phai cong them l1 else if((l1 + l2 ) >= cong[k][0]) bt(k+1, fee, 0, l0, l1+l2-cong[k][0]); // 3 quan deu tham chien else bt(k+1, fee, 0, l0 + l1 + l2 - cong[k][0] , 0); } } } } int main(){ freopen("Text.txt", "r", stdin); int test; cin >> test; for(int tc =1; tc <= test; tc++){ cin >> N; for(int i=0; i<N; i++){ cin >> cong[i][0] >> cong[i][1]; } ans =100000; bt(0, 0, 0, 0, 0); cout << "#" << tc << " " << ans << endl; } return 0; }
Editor is loading...