Untitled
unknown
plain_text
2 years ago
1.7 kB
10
Indexable
#include <iostream> using namespace std; int N; int quan[21]; int cost[21]; int linh1 = 0, linh2 = 0, linh3 = 0; void Hugo(int chiphi, int k, int &min) { if(k == N) { if(min > chiphi) { min = chiphi; } return; } if(chiphi > min) { return; } for(int i = 0; i <= 2; i++) { if(i == 0) { // chon tra ve qua cong Hugo(chiphi + cost[k], k + 1,min); } else if( i == 1) { linh1 = linh1 + quan[k]; Hugo(chiphi + 2 * cost[k], k + 1, min); linh1 = linh1 - quan[k]; } else { if(linh1 + linh2 + linh3 >= quan[k]) { int t1 = linh1, t2 = linh2, t3 = linh3; int t = quan[k]; if(linh3 > 0) { if(linh3 >= t) { linh3 = linh3 - t; t = 0; } else { t = t - linh3; linh3 = 0; } } if(t > 0 && linh2 > 0) { if(linh2 >= t) { linh2 = linh2 -t; t = 0; } else { t = t - linh2; linh2 = 0; } } if(t > 0 && linh1 > 0) { if(linh1 >= t) { linh1 = linh1 - t; t = 0; } else { t = t - linh1; linh1 = 0; } } // cap nhat lai linh linh3 = linh2, linh2 = linh1, linh1 = 0; Hugo(chiphi, k + 1, min); linh1 = t1; linh2 = t2; linh3 = t3; } } } } int main() { int testcase; cin >> testcase; for(int tc = 1; tc <= testcase; tc++) { cin >> N; linh1 = linh2 = linh3 = 0; for(int i = 0; i < N; i++) { cin >> quan[i]; cin >> cost[i]; } int min = 100000; Hugo(0, 0, min); cout<<"#"<<tc<<" "<<min<<endl; } }
Editor is loading...