Untitled
unknown
plain_text
2 years ago
1.3 kB
7
Indexable
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]; } }
Editor is loading...