Untitled
unknown
plain_text
20 days ago
2.4 kB
1
Indexable
Never
#include <iostream> using namespace std; #define MAX 100000 struct Gate{ int vt; int guest; }; Gate gate[5]; int N, gateVisited[5], slot[100], kc[100]; int res; bool checkAllGate() { for (int i = 0; i < 3; i++) { if (gateVisited[i] == 0) return false; } return true; } void backTrack(int sum) { if (sum > res) return; if (checkAllGate()) { res = std::min(res, sum); return; } for (int i = 0; i < 3; i++) { if (gateVisited[i] == 1) continue; gateVisited[i] = 1; int vt = gate[i].vt; int guest = gate[i].guest; int numSpace = 1; int distance = 0; while (guest > 0) { if (guest > 0 && vt + distance <= N) { if (slot[vt + distance] == -1) { slot[vt + distance] = i; kc[vt + distance] = numSpace; sum += kc[vt + distance]; guest--; } } if (guest > 0 && vt + distance >= -1){ if (slot[vt - distance] == -1) { slot[vt - distance] = i; kc[vt - distance] = numSpace; sum += kc[vt - distance]; guest--; } } numSpace++; distance++; } if (guest == 0 ) backTrack(sum); for (int j = 1; j <= N; j++) { if (slot[j] == i) { slot[j] = -1; sum -= kc[j]; kc[j] = 0; } } vt = gate[i].vt; guest = gate[i].guest; numSpace = 1; distance = 0; while (guest > 0) { if (guest > 0 && vt + distance >= -1){ if (slot[vt - distance] == -1) { slot[vt - distance] = i; kc[vt - distance] = numSpace; sum += kc[vt - distance]; guest--; } } if (guest > 0 && vt + distance <= N) { if (slot[vt + distance] == -1) { slot[vt + distance] = i; kc[vt + distance] = numSpace; sum += kc[vt + distance]; guest--; } } numSpace++; distance++; } if (guest == 0 ) backTrack(sum); for (int j = 1; j <= N; j++) { if (slot[j] == i) { slot[j] = -1; sum -= kc[j]; kc[j] = 0; } } gateVisited[i] = 0; } } int main() { //freopen("in.txt", "r", stdin); int T; cin >> T; int tc = 1; while(T--) { cin >> N; for (int i = 0; i < 3; i++) { cin >> gate[i].vt >> gate[i].guest; gateVisited[i] = 0; } for (int i = 1; i < N; i++){ slot[i] = -1; kc[i] = 0; } res = MAX; backTrack(0); cout << "Case #" << tc++ << endl << res << endl; } return 0; }
Leave a Comment