hugovenhasol
#include <iostream> using namespace std; int n; struct door{ int solinh; int chiphi; }; door doors[100]; int quan[100]; int x[100]; int minans; int findpos(int index) { int counttd = 0; int tmpres = index; for (int i = index - 1; i >= 1; i--) { if (x[i] == 2) counttd += 1; if (counttd == 3) break; tmpres = i; } return tmpres; } int checkk(int pos, int index, int solinh) { int countt = 0; for (int i = pos; i <= index -1; i++) countt += quan[i]; if (countt >= solinh) return 1; return 0; } void update(int pos, int solinh) { while (solinh > 0) { if (solinh > quan[pos]) { solinh -= quan[pos]; quan[pos] = 0; } else { quan[pos] -= solinh; solinh = 0; } pos++; } } void update1(int index, int solinh) { index--; while (solinh > 0) { if (x[index] == 1) { int tmp = doors[index].solinh - quan[index]; if (solinh < tmp) { quan[index] += solinh; solinh = 0; } else { solinh -= tmp; quan[index] = doors[index].solinh; } } index--; } } void back(int index, int cost) { if (index == n + 1) { if (cost < minans) minans = cost; return; } if (cost >= minans) return; x[index] = 0; back(index + 1, cost + doors[index].chiphi); x[index] = 1; quan[index] = doors[index].solinh; back(index + 1, cost + 2*doors[index].chiphi); quan[index] = 0; int pos = findpos(index); if (checkk(pos, index, doors[index].solinh)) { x[index] = 2; //danh update(pos, doors[index].solinh); // xoa so quan chet back(index + 1, cost); update1(index, doors[index].solinh); // restore lai so quan chet } } int main() { int ntc; cin >> ntc; for (int tc=1; tc<=ntc; tc++) { cin >> n; for (int i = 1; i <= n; i++) cin >> doors[i].solinh >> doors[i].chiphi; minans = 999999; back(1,0); cout <<"#"<<tc << " "<< minans << endl; } return 0; }
Leave a Comment