作者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/m.aspx?n=bbs/Marginalman/M.1730359599.A.5CB.html