POJ 1160 Post Office：區間 DP 優化郵局選址最小化距離和

題目大意

V 個村莊（V≤300）位於數軸上，位置嚴格遞增。建 P 個郵局（P≤30, P≤V），郵局必須建在村莊位置。每村莊距離最近郵局的距離之和最小化，輸出最小總距離。

預處理：區間內建一郵局的最小距離和

對區間 [i, j]（1-based），最優郵局位置為中位數村莊 mid = (i+j)/2。
cost[i][j] = Σ_{k=i}^{j} |pos[k] - pos[mid]|。
可用遞推 O(V²) 計算：
cost[i][i] = 0
cost[i][j] = cost[i][j-1] + pos[j] - pos[(i+j)/2]（新增村莊 j 到中位數的距離）。

DP 定義與轉移

dp[i][k]：前 i 個村莊建 k 個郵局的最小總距離。
轉移：dp[i][k] = min_{t=k-1}^{i-1} (dp[t][k-1] + cost[t+1][i])。
初始：dp[i][1] = cost[1][i]，dp[0][0] = 0，其餘 INF。
答案：dp[V][P]。

複雜度

預處理 O(V²)，DP O(V² P) ≈ 300²×30 = 2.7×10⁶，極快。

參考代碼（C++）