UVA 662 Fast Food：DP 優化倉庫選址

題目大意

n (≤200) 家餐廳位於高速公路上（位置遞增），選 k (≤30) 家建倉庫，每家餐廳分配到最近倉庫。最小化總距離和。需輸出最優方案與總距離。

DP 狀態定義

• `dp[i][j]`：前 i 家餐廳建 j 倉庫的最小總距離
• 轉移：`dp[i][j] = min_{j-1 ≤ p < i} (dp[p][j-1] + cost(p+1, i))`
• `cost(l, r)`：第 l~r 家餐廳共用一倉庫的最小距離和（倉庫建在中位數位置）

Cost 預計算

int d[205]; // 1-based 餐廳位置
int cost[205][205];

void precompute(int n) {
    for (int i = 1; i <= n; ++i)
        for (int j = i; j <= n; ++j) {
            int mid = (i + j) >> 1;
            int sum = 0;
            for (int k = i; k <= j; ++k)
                sum += abs(d[mid] - d[k]);
            cost[i][j] = sum;
        }
}

DP 與路徑記錄

int dp[205][35], path[205][35];

void solve(int n, int k) {
    const int INF = 1e9;
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= k; ++j)
            dp[i][j] = INF;
    
    for (int i = 1; i <= n; ++i) {
        dp[i][1] = cost[1][i];
        path[i][1] = 0;
    }
    
    for (int i = 1; i <= n; ++i)
        for (int j = 2; j <= k; ++j)
            for (int p = j-1; p < i; ++p)
                if (dp[p][j-1] + cost[p+1][i] < dp[i][j]) {
                    dp[i][j] = dp[p][j-1] + cost[p+1][i];
                    path[i][j] = p;
                }
}

void print_solution(int n, int k) {
    vector depots;
    int cur = n;
    for (int i = k; i >= 1; --i) {
        int p = path[cur][i];
        int depot_idx = (p + 1 + cur) / 2; // 中位數餐廳索引
        depots.push_back(depot_idx);
        cur = p;
    }
    reverse(depots.begin(), depots.end());
    // 輸出格式...
}

複雜度

• Cost 預計算：O(n³) = 8×10⁶，可接受
• DP：O(n²k) = 200²×30 = 1.2×10⁶
• 總體：~10⁷ 操作，極快

優化：四邊形不等式 / Knuth 優化

若 n 更大（如 10⁴），可利用 `cost` 滿足四邊形不等式，將 DP 優化至 O(nk) 或 O(nk log n)。本題 n=200 無需優化。

輸出格式細節

Chain 1
Depot 1 at restaurant 2 serves restaurants 1 to 3
Depot 2 at restaurant 4 serves restaurants 4 to 5
Depot 3 at restaurant 6 serves restaurant 6
Total distance sum = 8

注意單複數：`restaurant` vs `restaurants`。