huguquanlytautu
quoc14
c_cpp
a month ago
2.6 kB
3
Indexable
Never
caidat
#include <iostream> using namespace std; int n; int minans; struct Door{ int posDoor; int cCus; }; int kt[3]; Door doors[4]; int isset[10002]; int tt[4]; void backtrack(int index, int sumd) { if (index == 4) { if (minans > sumd) minans = sumd; /* for (int i = 0; i <= n+1; i++) cout << isset[i] <<" "; cout << sumd << endl;*/ return; } int iddoor = tt[index]; Door curent = doors[iddoor]; int left = curent.posDoor; int right = curent.posDoor; for (int i = 1; i < curent.cCus; i++) { while (isset[left] != 0 && left>0) left--; while (isset[right] != 0 && right <= n) right++; if (left == 0) { isset[right++] = iddoor; sumd += right - curent.posDoor; } else if (right == n+1) { isset[left--] = iddoor; sumd += curent.posDoor - left; } else { if (curent.posDoor - left < right - curent.posDoor) { isset[left--] = iddoor; sumd += curent.posDoor - left; } else { isset[right++] = iddoor; sumd += right - curent.posDoor; } } } while (isset[left] != 0 && left>0) left--; while (isset[right] != 0 && right <= n) right++; if (left == 0) { isset[right++] = iddoor; sumd += right - curent.posDoor; backtrack(index+1,sumd); } else if (right == n+1) { isset[left--] = iddoor; sumd += curent.posDoor - left; backtrack(index+1, sumd); } else { if (curent.posDoor - left == right - curent.posDoor) { sumd += curent.posDoor - left + 1; isset[left] = iddoor; backtrack(index+1, sumd); isset[left] = 0; isset[right] = iddoor; backtrack(index+1, sumd); } else { if (curent.posDoor - left < right - curent.posDoor) { isset[left--] = iddoor; sumd += curent.posDoor - left; } else { isset[right++] = iddoor; sumd += right - curent.posDoor; } backtrack(index+1, sumd); } } for (int i = 1; i <= n; i++) if (isset[i] == iddoor) { isset[i] = 0; } } void back(int index) { if (index == 4) { backtrack(1, 0); return; } for (int i = 1; i<=3; i++) if (kt[i] == 0) { kt[i] = 1; tt[index] = i; back(index + 1); kt[i] = 0; } } int main() { // freopen("input.txt","r",stdin); int ntc; cin >> ntc; for (int tc=1; tc<=ntc; tc++) { cin >> n; for (int i = 1; i <= 3; i++) cin >> doors[i].posDoor >> doors[i].cCus; minans = 9999999; back(1); cout << "Case #"<<tc << endl << minans << endl; } //back(1); return 0; }
Leave a Comment