BZOJ 3675 [APIO2014] 序列分割 - 斜率優化 DP 詳解

問題描述

長度 n (≤ 100,000) 的非負整數序列，需分割成 k+1 (k ≤ 200) 個非空連續子序列。每次分割一個長度 > 1 的序列為兩段，得分為兩段元素和的乘積。k 輪後總分最大化。

關鍵結論：分割順序不影響最終得分

證明：最終得分 = Σ_i<j (sum[i] * sum[j])，其中 sum[i] 為第 i 段的和。這與分割順序無關，只取決於最終分段位置。因此問題轉化為：選擇 k 個分割點，最大化總得分。

DP 定義

f[i][j]：前 i 個數分成 j 段的最大得分。前綴和 sum[i]。

f[i][j] = max_{k
展開：f[k][j-1] + sum[k]*sum[i] - sum[k]²
對於固定 j 和 i，sum[i] 是常數。設 g[k] = f[k][j-1] - sum[k]²，則：
f[i][j] = max_k { g[k] + sum[k] * sum[i] }

斜率優化（凸包技巧）
將每個 k 視為平面上點 (x=sum[k], y=g[k])。對於給定 X = sum[i]，求最大化 y + x*X，即斜率為 -X 的直線截距最大值。維護下凸包，單調隊列決策單調性。

決策單調性證明
因 sum[i] 遞增，查詢斜率 -sum[i] 遞減。凸包上最優決策點單調右移，可用雙端隊列 O(1) 彈出隊首/隊尾。

完整代碼實現
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100005;
long long sum[MAXN], f[MAXN], g[MAXN];
int q[MAXN];

int main() {
    int n, m; scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; ++i) {
        scanf("%lld", &sum[i]);
        sum[i] += sum[i-1];
    }
    
    while (m--) {  // m = k
        for (int i = 1; i <= n; ++i) g[i] = sum[i]*sum[i] - f[i];
        
        int h = 1, t = 0;
        for (int i = 1; i <= n; ++i) {
            // 維護凸包：隊尾新點 i 與倒數兩點判斷
            while (h < t && 
                (g[q[t]] - g[q[t-1]]) * (sum[i] - sum[q[t]]) 
                >= (g[i] - g[q[t]]) * (sum[q[t]] - sum[q[t-1]]))
                --t;
            q[++t] = i;
            
            // 隊首決策：斜率單調，彈出不再優的隊首
            while (h < t && 
                g[q[h+1]] - g[q[h]] < (sum[q[h+1]] - sum[q[h]]) * sum[i])
                ++h;
            
            f[i] = g[q[h]] + sum[q[h]] * sum[i];
        }
    }
    printf("%lld\n", f[n]);
    return 0;
}

關鍵細節

空間優化：滾動數組，f 只保留上一輪結果
斜率比較避免除法：交叉相乘防精度丟失
隊列存下標，通過 sum[] 和 g[] 計算幾何量
初始 f[i] = 0 對應 0 次分割（1 段）得分為 0


複雜度

時間：O(k n)，k ≤ 200, n ≤ 100,000 → 2×10⁷ 操作，極快
空間：O(n)


樣例驗證
輸入：7 3 / 4 1 3 4 0 2 3
最優分段：[4] [1,3] [4,0] [2,3]，得分 = 4×13 + 4×9 + 4×5 = 52+36+20 = 108。代碼輸出 108。