斜率優化 DP 專題：BZOJ 1911 特別行動隊（APIO 2010）

題目大意

序列 `a[1..n]`，將其分段，每段得分 `A*(sum)^2 + B*sum + C`，求最大總分。n ≤ 1e6。

DP 方程

`dp[i] = max{ dp[j] + A*(S[i]-S[j])² + B*(S[i]-S[j]) + C }`，`S[i]` 為前綴和。

斜率優化推導

展開平方：

dp[j] + A(S[i]² - 2S[i]S[j] + S[j]²) + B(S[i]-S[j]) + C
= (dp[j] + A S[j]² - B S[j]) - 2A S[i] S[j] + (A S[i]² + B S[i] + C)

設 `k > j` 且 `k` 優於 `j`：

(dp[k] + A S[k]² - B S[k]) - 2A S[i] S[k] > (dp[j] + A S[j]² - B S[j]) - 2A S[i] S[j]
2A S[i] (S[k] - S[j]) < (dp[k]-dp[j]) + A(S[k]²-S[j]²) - B(S[k]-S[j])
S[i] < [ (dp[k]-dp[j]) + A(S[k]²-S[j]²) - B(S[k]-S[j]) ] / [ 2A (S[k]-S[j]) ]

定義斜率：

slope(j,k) = [ (dp[k]-dp[j]) + A(S[k]²-S[j]²) - B(S[k]-S[j]) ] / [ 2A (S[k]-S[j]) ]

決策單調性：`S[i]` 遞增，維護下凸包，隊首斜率遞增。

完整代碼實現

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int MAXN = 1e6 + 5;

ll n, A, B, C;
ll a[MAXN], S[MAXN], dp[MAXN];
int q[MAXN], head, tail;

double slope(int j, int k) {
    ll num = dp[k] - dp[j] + A*(S[k]*S[k] - S[j]*S[j]) - B*(S[k] - S[j]);
    ll den = 2*A*(S[k] - S[j]);
    return (double)num / den;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    cin >> n;
    cin >> A >> B >> C;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        S[i] = S[i-1] + a[i];
    }
    
    head = tail = 0;
    q[0] = 0; dp[0] = 0;
    
    for (int i = 1; i <= n; i++) {
        // 隊首出隊：斜率 ≤ S[i] 的決策不優
        while (head < tail && slope(q[head], q[head+1]) <= S[i]) head++;
        
        int j = q[head];
        ll diff = S[i] - S[j];
        dp[i] = dp[j] + A*diff*diff + B*diff + C;
        
        // 隊尾入隊：維護下凸包
        while (head < tail && slope(q[tail-1], q[tail]) >= slope(q[tail], i)) tail--;
        q[++tail] = i;
    }
    
    cout << dp[n] << '\n';
    return 0;
}

關鍵點總結

1. 平方展開分組：將與 `i` 相關項提取，構造線性形式 `Y = M*X + B`
2. 斜率分式化簡：分子分母提取公因式，避免精度問題可用 `__int128` 交叉相乘
3. 單調隊列維護：`S[i]` 遞增 ⇒ 隊首單調出隊，決策點單調入隊
4. 複雜度：O(N) 時間，O(N) 空間，N=1e6 秒過

精度優化：整數交叉相乘

替代 `double slope`，判斷 `slope(a,b) >= slope(b,c)`：

bool bad(int a, int b, int c) {
    __int128 left  = (__int128)(dp[b]-dp[a] + A*(S[b]*S[b]-S[a]*S[a]) - B*(S[b]-S[a])) * (S[c]-S[b]);
    __int128 right = (__int128)(dp[c]-dp[b] + A*(S[c]*S[c]-S[b]*S[b]) - B*(S[c]-S[b])) * (S[b]-S[a]);
    return left >= right; // 下凸包
}

此題是斜率優化 DP 的「二次代價函數」標準模板，掌握「展開平方 → 線性化 → 斜率定義 → 凸包維護」完整流程，可解決同類分段優化問題。