序列分割問題：斜率優化動態規劃 C++ 實作詳解

題解：
不考慮極大資料範圍，首先可想出 DP 解法：dp[i][k] 表示前 i 個數字分成 k 段的最大分值。轉移方程：

dp[i][k] = max(dp[j][k-1] + sum[j] * (sum[i] - sum[j]))

這樣做顯然是 k × n² 演算法，對 100000 資料即使 k 只有 200 也會超時。需降低一維複雜度使演算法變為 n × k 複雜度。降低 DP 複雜度通常透過降低狀態轉移那一維（即枚舉 j）的複雜度，這就用到斜率優化。

根據斜率優化慣用做法，假設存在兩個決策點 k1, k2 且 k1 < k2，設在更新 i 點的 dp 值 dp[i][t+1] 時 k2 優於 k1，則存在：

dp[k1][t] + sum[k1] * (sum[i] - sum[k1]) < dp[k2][t] + sum[k2] * (sum[i] - sum[k2])

變形後得到：

(dp[k1][t] - sum[k1]²) - (dp[k2][t] - sum[k2]²)
--------------------------------------------------  < sum[i]
              sum[k2] - sum[k1]

記 slope[k1, k2] = 左邊式子，發現兩個性質：

1. 當 slope[k1, k2] < sum[i] 時，對 i 點 k2 決策優於 k1 且永遠優於 k1。因序列中每個數非負，對任意 x > i 有 sum[x] ≥ sum[i]，當 slope[k1, k2] < sum[i] 時必有 slope[k1, k2] < sum[x]，故每個決策具單調性：當 slope[k1, k2] < sum[i] 時，i 以後的點 k1 永遠無用。
2. 若存在 k1, k2, k3 且 k1 < k2 < k3，當 slope[k1, k2] > slope[k2, k3] 時，k2 決策點永遠不會用到。因為：假如更新某點 i 時 k2 比 k1 優，則 slope[k1, k2] < sum[i]；但同時因 slope[k1, k2] > slope[k2, k3]，故 slope[k2, k3] < sum[i]，即 k3 比 k2 優，所以 k2 沒用；假如 k2 沒有 k1 優，則 k2 直接沒用。因此不管怎樣 k2 都是沒用的。

擁有這兩個性質後，需維護一個佇列每次只存有用決策點來減少決策那一維時間複雜度。根據性質 2，維護的佇列 q 必須符合：slope[q1, q2] < slope[q2, q3] < slope[q3, q4] < ...，否則佇列會出現永遠無用決策點。

AC 程式碼（不需記錄路徑）

#include 
#include 
#define maxn (100005)
using namespace std;

int n, m, k, q[maxn];
long long sum[maxn], dp[maxn][2], y[maxn][2];

int main() {
    scanf("%d%d", &n, &k);
    for (int i = 1; i <= n; i++) {
        scanf("%lld", &sum[i]);
        sum[i] += sum[i-1];
    }
    for (int i = 1; i <= n; i++) y[i][0] = 0 - sum[i] * sum[i]; // dp[i][0] = 0
    for (int i = 1; i <= k; i++) {
        int now = i % 2;
        int pre = (i + 1) % 2;
        int h = 1, t = 1;
        q[h] = 1;
        for (int j = 1; j <= n; j++) {
            while (h < t && sum[j] * (sum[q[h+1]] - sum[q[h]]) >= (y[q[h]][pre] - y[q[h+1]][pre])) h++;
            dp[j][now] = dp[q[h]][pre] + sum[q[h]] * (sum[j] - sum[q[h]]);
            y[j][now] = dp[j][now] - sum[j] * sum[j];
            while (h < t && (y[q[t-1]][pre] - y[q[t]][pre]) * (sum[j] - sum[q[t]]) >= (y[q[t]][pre] - y[j][pre]) * (sum[q[t]] - sum[q[t-1]])) t--;
            t++; q[t] = j;
        }
    }
    printf("%lld\n", dp[n][k%2]);
    return 0;
}

UOJ 版本（需記錄路徑）

#include 
#include 
#define maxn (100005)
using namespace std;

int n, m, k, q[maxn], pr[maxn][202];
long long sum[maxn], dp[maxn][2], y[maxn][2];

int main() {
    scanf("%d%d", &n, &k);
    for (int i = 1; i <= n; i++) {
        scanf("%lld", &sum[i]);
        sum[i] += sum[i-1];
    }
    for (int i = 1; i <= n; i++) y[i][0] = 0 - sum[i] * sum[i];
    for (int i = 1; i <= k; i++) {
        int now = i % 2;
        int pre = (i + 1) % 2;
        int h = 1, t = 1;
        q[h] = 0;
        for (int j = 1; j <= n; j++) {
            while (h < t && sum[j] * (sum[q[h+1]] - sum[q[h]]) >= (y[q[h]][pre] - y[q[h+1]][pre])) h++;
            pr[j][i] = q[h];
            dp[j][now] = dp[q[h]][pre] + sum[q[h]] * (sum[j] - sum[q[h]]);
            y[j][now] = dp[j][now] - sum[j] * sum[j];
            while (h < t && (y[q[t-1]][pre] - y[q[t]][pre]) * (sum[j] - sum[q[t]]) >= (y[q[t]][pre] - y[j][pre]) * (sum[q[t]] - sum[q[t-1]])) t--;
            t++; q[t] = j;
        }
    }
    cout << dp[n][k%2] << endl;
    int d = n;
    for (int i = k; i >= 1; i--) {
        d = pr[d][i];
        // 記錄分割點
    }
    return 0;
}