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