DDSA
Advertisement

2463. Minimum Total Distance Traveled

2463.cs
C#
public class Solution
{
    public long MinimumTotalDistance(IList<int> robot, int[][] factory)
    {
        List<int> robots = new List<int>(robot);
        robots.Sort();
        Array.Sort(factory, (a, b) => a[0].CompareTo(b[0]));
        long[][][] mem = new long[robots.Count][][];
        for (int i = 0; i < robots.Count; i++)
        {
            mem[i] = new long[factory.Length][];
            for (int j = 0; j < factory.Length; j++)
                mem[i][j] = new long[robots.Count];
        }
        return MinimumTotalDistance(robots, factory, 0, 0, 0, mem);
    }

    private long MinimumTotalDistance(List<int> robot, int[][] factory, int i, int j, int k, long[][][] mem)
    {
        if (i == robot.Count)
            return 0;
        if (j == factory.Length)
            return long.MaxValue;
        if (mem[i][j][k] > 0)
            return mem[i][j][k];
        long skipFactory = MinimumTotalDistance(robot, factory, i, j + 1, 0, mem);
        int position = factory[j][0];
        int limit = factory[j][1];
        long useFactory = limit > k ? MinimumTotalDistance(robot, factory, i + 1, j, k + 1, mem) +
                                      Math.Abs(robot[i] - position)
                                      : long.MaxValue / 2;
        return mem[i][j][k] = Math.Min(skipFactory, useFactory);
    }
}
Advertisement
Was this solution helpful?