HDU 2829：DP + 四邊形不等式優化

四邊形不等式判定

w[i][j] 滿足四邊形不等式 ⟺ w[i+1][j] - w[i][j] 關於 j 遞減。本題 cost 滿足此條件。

優化模板：決策單調性 + 分治 DP

int S[MAXN][MAXN]; // S[i][j] = dp[i][j] 的最優決策點 k
void compute(int i, int l, int r, int optL, int optR) {
    if (l > r) return;
    int mid = (l+r)/2;
    int bestK = -1;
    dp[i][mid] = INF;
    for (int k = optL; k <= min(mid-1, optR); k++) {
        if (dp[i][mid] > dp[i-1][k] + cost[k+1][mid]) {
            dp[i][mid] = dp[i-1][k] + cost[k+1][mid];
            bestK = k;
        }
    }
    S[i][mid] = bestK;
    compute(i, l, mid-1, optL, bestK);
    compute(i, mid+1, r, bestK, optR);
}

代碼片段（關鍵部分）

for (int i=1;i<=m;i++) {
    dp[i][0]=0; S[i][n+1]=n;
    for (int j=n;j>=1;j--) {
        dp[i][j]=INF;
        int l=S[i-1][j], r=S[i][j+1];
        for (int k=l;k<=min(j-1,r);k++) {
            if (dp[i][j] > dp[i-1][k] + cost[k+1][j]) {
                dp[i][j] = dp[i-1][k] + cost[k+1][j];
                S[i][j]=k;
            }
        }
    }
}

關鍵點

• cost[i][j] 預計算：cost[i][j] = (sum[j-1]-sum[i-1])*sum[j] - (f[j-1]-f[i-1])。
• 決策單調性：S[i][j] ≤ S[i][j+1]，利用此性質縮小枚舉範圍。
• 空間可滾動數組優化至 O(n)。

總結

HDU 2829 展示了「四邊形不等式 → 決策單調性 → 縮小枚舉範圍」的經典 DP 優化鏈條。掌握此模板，可解決大量「分組/分割」類區間 DP 问题。