動態規劃求解：平面 n 點用 k 個底在 x 軸的矩形覆蓋最小面積（直方圖分割）

問題重述

• 給定 n 個點 (xᵢ, yᵢ)，yᵢ ≥ 0。
• 需用 **k 個矩形** 覆蓋所有點，矩形底邊在 x 軸上（即直方圖柱狀），面積 = 寬 × 高。
• 矩形不可重疊（邊界、頂點亦不可接觸）。
• 允許面積為 0（退化為垂直線段）。
• 目標：最小化 k 個矩形面積之和。

關鍵觀察：最優解構造性質

1. 將點按 x 座標排序：x₁ ≤ x₂ ≤ … ≤ xₙ。
2. 任意最優解中，每個矩形覆蓋一段**連續**的點區間 [l, r]。
   證明：若矩形覆蓋非連續點，中間空隙可縮小寬度減少面積，矛盾。
3. 區間 [l, r] 的最小覆蓋矩形：寬 = xᵣ - xₗ，高 = max(yₗ…yᵣ)。
4. 問題轉化為：**將有序序列分成 k 個連續段，最小化 ∑(xᵣ - xₗ) × max(y)**。

動態規劃定義

• `dp[i][j]`：前 i 個點（索引 1…i）分成 j 個矩形的最小面積和。
• 狀態轉移：
  `dp[i][j] = min_{t < i} { dp[t][j-1] + cost(t+1, i) }`
  其中 `cost(l, r) = (xᵣ - xₗ) * max(yₗ…yᵣ)`。
• 邊界：`dp[i][1] = cost(1, i)`；`dp[0][0] = 0`，其餘 `INF`。
• 答案：`dp[n][k]`。

優化：單調隊列 / 分治 DP / Convex Hull Trick

直接 DP 為 O(k n²)，n ≤ 5000 可接受；n ≤ 10⁵ 需優化。
觀察 `cost(l, r)` 滿足**四邊形不等式**與**單調性**，可用 **分治 DP** 將單層優化至 O(n log n)，總複雜度 O(k n log n)。

分治 DP 實現框架

void compute(int j, int l, int r, int optL, int optR) {
    if (l > r) return;
    int mid = (l + r) >> 1;
    pair<long, int> best = {INF, -1};
    for (int t = optL; t <= min(mid-1, optR); ++t) {
        long val = dp[t][j-1] + cost(t+1, mid);
        if (val < best.first) best = {val, t};
    }
    dp[mid][j] = best.first;
    int opt = best.second;
    compute(j, l, mid-1, optL, opt);
    compute(j, mid+1, r, opt, optR);
}

// 呼叫
for (int j = 2; j <= k; ++j)
    compute(j, 1, n, 1, n);

需預處理 `max(y)` 區間查詢（稀疏表 O(1) 或線段樹 O(log n)）。

特殊情況：k ≥ n

每點可單獨用一個寬度 0 的矩形（垂直線），總面積 = 0。若題目要求矩形寬度 > 0，則至少需相鄰點合併。

總結

1. 排序 → 連續分段 → DP。
2. 狀態 `dp[i][j]`，轉移 `min_{t} dp[t][j-1] + cost(t+1,i)`。
3. 利用四邊形不等式用分治 DP 加速至 O(k n log n)。
4. 實作細節：預處理 RMQ 求區間最大 y，處理邊界條件。

原最佳回答的貪婪「取前 k-1 點」在一般情況**不正確**，僅在 y 單調或特定分布下成立。嚴謹解需 DP。