NYOJ 737 石子合併：區間 DP + 四邊形不等式優化（O(N²)）

問題模型

N 堆石子排成一行，每次合併相鄰兩堆，代價為兩堆石子數之和，求合併成一堆的最小總代價。經典**區間 DP**。

基本 DP：O(N³)

• dp[i][j] = 合併區間 [i,j] 的最小代價。
• sum[i] = 前綴和，區間和 = sum[j]-sum[i-1]。
• 轉移：dp[i][j] = min(dp[i][k-1] + dp[k][j]) + sum(j)-sum(i-1)，k∈[i+1, j]。

四邊形不等式優化（Knuth 優化）

若代價函數滿足四邊形不等式與單調性，則最優決策點 opt[i][j] 滿足：
opt[i][j-1] ≤ opt[i][j] ≤ opt[i+1][j]。
因此枚舉 k 只需在 [opt[i][j-1], opt[i+1][j]] 範圍內，將 O(N³) 降為 O(N²)。

優化後代碼

#include <bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f;
const int MAXN = 300;

int dp[MAXN+1][MAXN+1];
int opt[MAXN+1][MAXN+1];
int sum[MAXN+1];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    while (cin >> n) {
        sum[0] = 0;
        for (int i = 1; i <= n; ++i) {
            int x; cin >> x;
            sum[i] = sum[i-1] + x;
            dp[i][i] = 0;
            opt[i][i] = i;
        }
        for (int len = 2; len <= n; ++len) {
            for (int i = 1; i + len - 1 <= n; ++i) {
                int j = i + len - 1;
                dp[i][j] = INF;
                int L = opt[i][j-1];
                int R = opt[i+1][j];
                for (int k = L; k <= R; ++k) {
                    int cost = dp[i][k-1] + dp[k][j] + sum[j] - sum[i-1];
                    if (cost < dp[i][j]) {
                        dp[i][j] = cost;
                        opt[i][j] = k;
                    }
                }
            }
        }
        cout << dp[1][n] << '\n';
    }
    return 0;
}

適用條件驗證

石子合併代價函數 w(i,j) = sum[j]−sum[i−1] 滿足四邊形不等式與單調性，故 Knuth 優化正確。