Untitled

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;
}