作者JIWP (神楽めあ的钱包)
看板Marginalman
标题Re: [闲聊] 每日leetcode
时间Thu Oct 31 15:26:37 2024
2463. Minimum Total Distance Traveled
array : robot，robot[i]为第i个机器人一开始的位置
array : factory
factory[j][0]为第j个工厂的位置、factory[j][1]为第j个工厂可以修理的机器人上限
每个机器人的位置一开始不会重复
每个工厂的位置也不会重复
可以让机器人往左或往右走
当机器人相遇时不会发生碰撞
当工厂达到修理上限时机器人就不能在进去
请问要让所有机器人都可以被修理所需要移动的最短距离
思路:
先将robot、factory透过位置进行排序
函式dfs(i,j)回传从第i个机器人、第j个工厂开始修理需要的最短距离
并用dp[i][j]纪录dfs(i,j)的值
如果第j的工厂不修理机器人那
dfs(i,j)=dfs(i,j+1) (factory[j]修理0个机器人的情况)
接着我们从k=0~factory[j][1]-带入下式 (表示factory[j]修理k+1个机器人)
dfs(i,j)=min( dfs(i+k+1,j+1)) + Σ(t=0~k)abs(robot[i+t] - factory[j][0]) )
这样就可以得到答案了
golang code :
func minimumTotalDistance(robot []int, factory [][]int) int64 {
n, m := len(robot), len(factory)
slices.Sort(robot)
slices.SortFunc(factory, func(a, b []int) int {
return a[0] - b[0]
})
dp := make([][]int, n)
for i := 0; i < n; i++ {
dp[i] = make([]int, m)
}
var dfs func(int, int) int
dfs = func(robot_i, factory_j int) int {
if robot_i == n {
return 0
}
if factory_j == m {
return 1e13
}
if dp[robot_i][factory_j] != 0 {
return dp[robot_i][factory_j]
}
ans := dfs(robot_i, factory_j+1)
step := 0
for k := 0; k < factory[factory_j][1]; k++ {
if k+robot_i >= n {
break
}
step += abs(robot[robot_i+k] - factory[factory_j][0])
ans = min(ans, dfs(robot_i+1+k, factory_j+1)+step)
}
dp[robot_i][factory_j] = ans
return ans
}
return int64(dfs(0, 0))
}
func abs(i int) int {
if i < 0 {
return -i
}
return i
}
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 111.71.213.179 (台湾)
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Marginalman/M.1730359599.A.5CB.html