1樓：一鯨
// Helper function: 定義域為二維整數空間的函式的 memoize 高階函式
const
memoize2D
=func
=>;};
// Helper function: 生成整數閉區間
const
range=(
l,r)
=>newArray(r
-l+1
).fill(0
).map((_
,i)=>i+
l);// Minimal Overall Distance
const
minDist
=arr
=>num=>
);// Memoized function: 居民區 i, j (i < j) 的中間居民區 m:
// 居民區 m 離 i 更近
// 居民區 m + 1 離 j 更近
const
mid=
memoize2D((i
,j)=>);// 動態規劃狀態
// p 個郵局，最右乙個設在居民區 r，r 之左所有居民區到達郵局的最小總距離
constst=
memoize2D((r
,p)=>));});
// 遍歷所有從 num - 1，到 arr.length - 1 的居民區，分別作為最右郵局的位置，
// 加上右側剩餘居民區的距離，計算最佳分配方案
return
Math
.min
(...
range
(num-1
,arr
.length-1
).map(i
=>st(
i,num)
+dist(i
,arr
.length-1
),));};
2樓：hzcool
經典題了，dp[i][j]前面i個點選了j個郵局的最小總距離。
dp[i][j]=min(dp[k][j-1]+cost(k+1,i))
後面cost(k+1,i)，就是這個區間的點到它們中位數的距離和，預處理字首和、字首和的字首和就可以O(1)得到，總時間複雜度O(n^3)。
優化 ：決策單調性， 這個轉移是決策單調的，所以可以時間複雜度優化到O(n^2)。還不夠，這個題還可以用wqs帶權二分優化到O(nlogn)。
3樓：JiBao
個人覺得這個是區間動態規劃，dp[l][r][m]表示在區間l到r放m個郵局的最小值，初步估計一下，應該是N的3方時間複雜度
具體過程還沒想好，等有時間在細看
我們和一艘飛船在一條直線上，如果該飛船以光速向我們靠近或遠離，根據相對論，我們會看到什麼景象呢？
xu Jyric 1，根據狹義相對論，船不可能達到真空中的光速 2，如果船以接近光速的速度飛向我們，那麼我們會看到 船以接近光速的速度飛向我們 以上。 鋼鐵怪獸 如果它是光速的話在我們開到它時它已經飛過地球了。不到光速的話我們只有當光傳播到我們這裡才能看見。比如說這個飛船會發光而且是玻璃透明材質的話...
一條直線上的點和乙個平面上的點哪個多？
搬磚的 這個問題在一兩百年前有個好像是德國的數學家就已經解決了，他把無窮數分為三個等級。還證明了線段上的點數大於平面上的點數，這點與我們的直覺相反。小時候看過一本介紹的書，但搞忘了書名。 幽靈代筆 這個問題的關鍵是數學上規定 多少 的概念是什麼？一樣多在數學上是如何被約定的？遠古的時代，人們要確定多...
我大腿和小腿為什麼不在一條線上？
IMBODY 因為你小腿外側用的比較多。用進廢退，天長日久很自然小腿外側的肌肉更發達，所以看上去，小腿肚的肌肉往外翻，影響腿型。那怎麼辦呢？辦法也很簡單 改變雙腳用力方式，讓腳掌均勻受力。腳底有三個受力點。小腿肚外翻的人，不管是站著 走路 或者是跑步，總之一切腳支撐的行為都會把身體的重力更多的放在1...