2463.最小移动总距离

链接：2463.最小移动总距离
难度：Hard
标签：数组、动态规划、排序
简介：请你返回所有机器人移动的最小总距离。测试数据保证所有机器人都可以被维修。

题解 1 - cpp

• 编辑时间：2022-11-10
• 执行用时：40ms
• 内存消耗：8.2MB
• 编程语言：cpp
• 解法介绍：dp[i][j] = 当只有 i 个工厂，j 个机器人时的最小移动距离。

class Solution {
public:
    const int MAX = 105;
    long long minimumTotalDistance(vector<int>& robot, vector<vector<int>>& factory) {
        sort(robot.begin(), robot.end());
        sort(factory.begin(), factory.end(), [](auto &a, auto &b){ return a[0] < b[0]; });
        int n = factory.size(), m = robot.size();
        // dp[i][j] = 当只有i个工厂，j个机器人时的最小移动距离
        long long dp[MAX][MAX];
        memset(dp, 0x3f, sizeof(long long) * MAX * MAX);
        for (int i = 0; i <= n; i++) dp[i][0] = 0;
        for (int i = 1; i <= n; i++) {
            auto &f = factory[i - 1];
            for (int j = 1; j <= m; j++) {
                // 当前工厂不做操作的时候 等于 前一个工厂
                dp[i][j] = dp[i - 1][j];
                long long sum = 0;
                for (int k = j; k >= max(1, j - f[1] + 1); k--) {
                    sum += abs(robot[k - 1] - f[0]);
                    dp[i][j] = min(dp[i][j], sum + dp[i - 1][k - 1]);
                }
                // for (int k = 1; k <= min(j, f[1]); k++) {
                //     sum += abs(robot[j - k] - f[0]);
                //     dp[i][j] = min(dp[i][j], sum + dp[i - 1][j - k]);
                // }
            }
        }
        return dp[n][m];
    }
};