Untitled

mail@pastecode.io avatar
unknown
java
2 years ago
1.3 kB
1
Indexable
Never
class Solution {
    public long minimumTotalDistance(List<Integer> robot, int[][] factory) {
        Collections.sort(robot);
        List<Integer> sort = new ArrayList<>();
        for (int i = 0; i < factory.length; i++) {
            sort.add(i);
        }
        Collections.sort(sort, (a, b) -> factory[a][0] - factory[b][0]);
        int N = robot.size(), M = factory.length;
        long[][] dp = new long[M + 1][N + 1];
        for (int i = 0; i <= M; i++) {
            Arrays.fill(dp[i], Long.MAX_VALUE);
        }
        dp[0][0] = 0;
        for (int i = 1; i <= M; i++) {
            dp[i][0] = dp[i - 1][0];
            for (int j = 1; j <= N; j++) {
                dp[i][j] = dp[i - 1][j];
                long sum = 0;
                for (int k = j; k >= 1; k--) {
                    if (j - k + 1 > factory[sort.get(i - 1)][1]) {
                        break;
                    }
                    sum += Math.abs((long)factory[sort.get(i - 1)][0] - robot.get(k - 1));
                    if (dp[i - 1][k - 1] != Long.MAX_VALUE) {
                        dp[i][j] = Math.min(dp[i][j], dp[i - 1][k - 1] + sum);
                    }
                }
            }
        }
        return dp[M][N];
    }
}