POJ 1160 Post Office：郵局選址經典 DP

初始化：dp[1][j] = cost[1][j]。答案 dp[P][V]。

複雜度優化

• 朴素 DP：O(P * V²)，30 * 300² = 2.7e6，完全可行。
• 可用四邊形不等式優化至 O(P * V log V) 或 O(P * V)，但非必要。

參考代碼 (C++)

#include 
using namespace std;
const int INF = 0x3f3f3f3f;
int pos[305], cost[305][305], dp[35][305];

int main() {
    int V, P;
    while (cin >> V >> P) {
        for (int i = 1; i <= V; ++i) cin >> pos[i];
        for (int i = 1; i <= V; ++i) {
            cost[i][i] = 0;
            for (int j = i+1; j <= V; ++j)
                cost[i][j] = cost[i][j-1] + pos[j] - pos[(i+j)/2];
        }
        memset(dp, 0x3f, sizeof(dp));
        for (int j = 1; j <= V; ++j) dp[1][j] = cost[1][j];
        for (int k = 2; k <= P; ++k)
            for (int j = k; j <= V; ++j)
                for (int i = k-1; i < j; ++i)
                    dp[k][j] = min(dp[k][j], dp[k-1][i] + cost[i+1][j]);
        cout << dp[P][V] << '\n';
    }
    return 0;
}

關鍵點總結

• 中位數性質將區間成本預處理為 O(V²)。
• DP 狀態定義清晰：前綴村莊 + 郵局數。
• 初始化 dp[1][j] 是關鍵基礎情況。
• 數據範圍小，三重循環無需優化即可 AC。