leetcode

0 class Solution {

1 public:

2 long long minimumTotalDistance(vector<int> &robot, vector<vector<int>> &factory) const {

3 sort(begin(factory), end(factory));

4 sort(begin(robot), end(robot));

5

6 vector<int> positions;

7 for (const auto &f : factory) {

8 for (int i = 0; i < f[1]; i++) {

9 positions.push_back(f[0]);

10 }

11 }

12

13 const int n = size(robot), m = size(positions);

14 static long long dp[10001];

15

16 memset(dp, 0x00, sizeof(dp));

17 dp[m] = 1e12;

18 for (int i = n - 1; i >= 0; i--) {

19 long long prev = i != n - 1 ? 1e12 : 0;

20 for (int j = m - 1; j >= 0; j--) {

21 long long assign = abs(robot[i] - positions[j]) + prev;

22 long long skip = dp[j + 1];

23

24 prev = dp[j];

25 dp[j] = min(assign, skip);

26 }

27 }

28

29 return dp[0];

30 }

31 };