Untitled

mail@pastecode.io avatar
unknown
plain_text
a year ago
1.3 kB
2
Indexable
Never
#include<iostream>
using namespace std;
const int MaxL = 25;
int TC, N, bs[MaxL], cp[MaxL], minc, a[MaxL], sv[MaxL];

int getSa() {
	int sum = 0;
	for(int i = 0; i < N; i++) if(a[i] > 0 && sv[i] < 3) sum += a[i];
	return sum;
}

void doing(int k, int c) {
	if(c >= minc) return;
	if(k == N) {
		if(c < minc) minc = c;
		return;
	}
	doing(k + 1, c + cp[k]);
	a[k] = bs[k];
	doing(k + 1, c + 2 * cp[k]);
	a[k] = 0;
	int s = getSa();
	if(s >= bs[k]) {
		int stmp = bs[k];
		int tmp1[MaxL], tmp2[MaxL];
		for(int i = 0; i < N; i++) tmp1[i] = sv[i];
		for(int i = 0; i < N; i++) tmp2[i] = a[i];
		for(int i = 0; i < N; i++) if(a[i] > 0) sv[i]++;
		for(int i = 0; i < N; i++)
			if(a[i] > 0 && sv[i] < 4)
				if(stmp >= a[i]) {
					stmp -= a[i]; 
					a[i] = 0;
				} else {
					a[i] -= stmp;
					stmp = 0;
				}
		doing(k + 1, c);
		for(int i = 0; i < N; i++) sv[i] = tmp1[i];
		for(int i = 0; i < N; i++) a[i] = tmp2[i];
	}
}

int main() {
	/*freopen("input.txt", "r", stdin);*/
	cin >> TC;
	for(int tc = 0; tc < TC; tc++) {
		cin >> N;
		minc = 2147483646;
		fill_n(a, N, 0); fill_n(sv, N, 0);
		for(int i = 0; i < N; i++) cin >> bs[i] >> cp[i];
		doing(0, 0);
		cout << "#" << tc + 1 << " " << minc << endl;
	}
	return 0;
}