Untitled
unknown
plain_text
23 days ago
1.4 kB
2
Indexable
Never
#include <iostream> using namespace std; int T, N; int sol[25]; int price[25]; int ans; int minA; int num; int sol0, sol1, sol2; void backtrack(int k){ if(k == N){ if(ans < minA){ minA = ans; } return; } if(ans >= minA){ return; } for(int i = 0; i < 3; i++){ if(i == 0){ ans += price[k]; backtrack(k + 1); ans -= price[k]; } if(i == 1){ ans += price[k] * 2; sol0 += sol[k]; backtrack(k + 1); ans -= price[k] * 2; sol0 -= sol[k]; } if(i == 2){ if(sol0 + sol1 + sol2 >= sol[k]){ int s1 = sol0; int s2 = sol1; int s3 = sol2; if(sol2 >= sol[k]){ sol2 = sol1; sol1 = sol0; sol0 = 0; }else if(sol2 + sol1 >= sol[k]){ sol2 = sol2 + sol1 - sol[k]; sol1 = sol0; sol0 = 0; }else if(sol2 + sol1 + sol0 >= sol[k]){ sol1 = sol2 + sol1 + sol0 - sol[k]; sol2 = 0; sol0 = 0; } backtrack(k + 1); sol0 = s1; sol1 = s2; sol2 = s3; } } } } int main(){ freopen("input.txt" ,"rt", stdin); cin >> T; for(int tc = 1; tc <= T; tc++){ cin >> N; for(int i = 0; i < N; i++){ cin >> sol[i] >> price[i]; } minA = 1000000; ans = 0; num = 0; sol1 = sol2 = sol0 = 0; backtrack(0); cout << "#" << tc << " " << minA << endl; } return 0; }
Leave a Comment