Hugo_venha
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