Hugo_venha

 avatar
duyvan
plain_text
24 days ago
1.5 kB
3
Indexable
Never
#include<stdio.h>
int N,T;
int a[20][2];
int ans;
int sllinh[3];
int solinh;
//0: con 1 luot danh
//1: con 2 luot danh
//2: con 3 luot danh
void bt(int chiphi, int n){
	int i;
	if(n==N){
		if(chiphi<ans)
			ans = chiphi;
		return;
	}
	if(chiphi>=ans){
		return;
	}
	for(i=0;i<3;i++){
		int k;
		if(i==0){ // pass
			bt(chiphi+a[n][1],n+1);
		}else if(i==1){ // thue
			int temp = sllinh[2];
			sllinh[2] += a[n][0];
			bt(chiphi+a[n][1]*2,n+1);
			sllinh[2] = temp;
		}else{ // danh
			solinh = sllinh[0] + sllinh[1] + sllinh[2];
			if(a[n][0]<=solinh){
				int t0 = sllinh[0];
				int t1 = sllinh[1];
				int t2 = sllinh[2];
				//int sl = solinh;
				int dich = a[n][0];
				int j;
				for(j=0;j<3;j++){
					if(sllinh[j] != 0){
						if(sllinh[j] >= dich){
							sllinh[j] -= dich;
							dich=0;
							//break;
						}else{
							dich -= sllinh[j];
							sllinh[j] = 0;
						}
					}
				}
				sllinh[0] = sllinh[1];
				sllinh[1] = sllinh[2];
				sllinh[2] = 0;
				//solinh = sllinh[0] + sllinh[1];
				bt(chiphi,n+1);
				//solinh = sl;
				sllinh[0] = t0;
				sllinh[1] = t1;
				sllinh[2] = t2;
			}
		}
	}
}

int main(){
	//freopen("input.txt","r",stdin);
	int tc,i;
	scanf("%d",&T);
	for(tc=0;tc<T;tc++){
		scanf("%d",&N);
		for(i=0;i<N;i++){
			// 0: so linh
			// 1: chi phi thue
			scanf("%d %d",&a[i][0], &a[i][1]);
		}
		solinh=0;
		ans=999999;
		bt(0,0);
		printf("#%d %d\n",tc+1, ans);
	}
	return 0;
}
Leave a Comment