Untitled
unknown
plain_text
16 days ago
1.4 kB
7
Indexable
Never
#include<iostream> using namespace std; #define min(a, b) a < b ? a : b #define INF 100000000 #define MAX 25 int N; int infor[MAX][2]; int visited[MAX]; int ans, s0, s1, s2; void backtrack(int k, int csum) { int add, cnt; add = 0; if(csum >= ans) return; if(k == N) { ans = min(ans, csum); return; } for(int i = 0; i < 3; i++) { if(i == 0) { add = infor[k][1]; backtrack(k + 1, csum + add); } else if(i == 1) { add = 2 * infor[k][1]; s0 += infor[k][0]; backtrack(k + 1, csum + add); s0 -= infor[k][0]; } else { int t2 = s2, t1 = s1, t0 = s0; int total = infor[k][0]; if(s0 + s1 + s2 >= total) { if(s2 >= total) { s2 = s1; s1 = s0; s0 = 0; } else if(s2 + s1 >= total) { s2 = s2 + s1 - total; s1 = s0; s0 = 0; } else { s1 = s2 + s1 + s0 - total; s2 = 0; s0 = 0; } backtrack(k + 1, csum); s2 = t2; s1 = t1; s0 = t0; } } } } int main() { int tc; int T; freopen("input.txt", "r", stdin); cin >> T; for(tc = 1; tc <= T; ++tc) { cin>>N; for(int i = 0; i < N; i++) { cin>>infor[i][0]>>infor[i][1]; } ans = INF; s0 = s1 = s2 = 0; backtrack(0, 0); cout<<"#"<<tc<<" "<<ans<<endl; } return 0; }
Leave a Comment