main.cpp (2415B)
1 #include <iostream> 2 #include <climits> 3 #include <bitset> 4 #include <vector> 5 6 // - thoughts: 7 // - there are objects in a room that have to be placed in a container 8 // - the girl can only carry at most two objects at a time 9 // - container can't move 10 // - if an object is picked up, it must be moved directly to the handbag, not pickup / set down 11 // - cover distance between two objects in time equal to squared length of the segment connecting the objects 12 // - euclidean distance squared 13 // - girl starts at the handbag 14 // - find operations that minimizes time to get all objects in container 15 16 // this feels dp. 17 18 // what's the state? 19 // s(visited, holding, position) 20 // where visited is a bitmask 21 // at most 24 bits 22 23 using namespace std; 24 25 int distance(int x1,int y1,int x2,int y2) { 26 return ((x2-x1) * (x2-x1)) + ((y2-y1) * (y2-y1)); 27 } 28 29 int solve(vector<int>& xVals, vector<int>& yVals, bitset<24> current, int holding, int x, int y, int cx, int cy, vector<int>& memo) { 30 31 if(holding == 0 && memo[current.to_ulong()] != -1) { 32 return memo[current.to_ulong()]; 33 } 34 35 int shortest = INT_MAX; 36 bool found = false; 37 38 if(holding < 2) { 39 for(int i = 0; i < xVals.size(); ++i) { 40 if(current[i] == 0) { 41 bitset<24> updated = current; 42 updated[i] = 1; 43 int dist = distance(x,y,xVals[i], yVals[i]); 44 int cv = solve(xVals,yVals,updated, holding+1, xVals[i],yVals[i], cx, cy, memo); 45 shortest = min(cv+dist,shortest); 46 found = true; 47 } 48 } 49 } 50 51 if(holding > 0) { 52 int dist = distance(x,y,cx,cy); 53 int cv = solve(xVals,yVals,current, 0, cx,cy, cx, cy, memo); 54 shortest = min(cv+dist,shortest); 55 found = true; 56 } 57 58 if(!found) { 59 return 0; // done 60 } 61 62 if(holding == 0) { 63 memo[current.to_ulong()] = shortest; 64 } 65 66 return shortest; 67 } 68 69 int main() { 70 int n, hx, hy, cx, cy = 0; 71 72 cin >> hx; 73 cin >> hy; 74 75 cin >> n; 76 77 vector<int> xVals{}; 78 vector<int> yVals{}; 79 80 for(int i = 0; i < n; ++i) { 81 cin >> cx; 82 cin >> cy; 83 xVals.push_back(cx); 84 yVals.push_back(cy); 85 } 86 87 bitset<24> current {}; 88 89 vector<int> memo(1 << n, -1); 90 91 cout << solve(xVals,yVals,current, 0, hx,hy, hx, hy, memo) << endl; 92 }