斜率优化 DPCSP-S

💡 核心思想

斜率优化 DP 用于解决转移方程形如 dp[i] = min{ dp[j] + (prefix[i] - prefix[j])^2 } + C 的问题。核心思想是将 DP 方程变形为 y = kx + b 的直线形式，把每个决策点 j 看作平面上的点，用凸包（上凸壳或下凸壳）维护最优决策点集，将 O(n²) 优化到 O(n) 或 O(n log n)。

🎯 直觉理解

想象你在选股票：每个历史价格是一个点，你要找"性价比最高"的那个点。斜率优化就是维护一个"凸包"——就像用双手包住一堆点，只保留最外围的点，内部的点永远不可能成为最优解。查询时，根据当前直线的斜率，在凸包上找到切点。

📝 算法流程

1. 写出原始 DP 方程
2. 整理为 y = kx + b 的形式：令 y_j = dp[j] + prefix[j]^2, x_j = prefix[j]
3. dp[i] = min{ y_j - 2*prefix[i]*x_j } + prefix[i]^2 + C
4. 斜率：判断点 j1, j2, j3 是否共线或形成上/下凸壳
5. 用单调队列维护凸包：新点入队时，检查队尾两点与新点是否满足凸性
6. 查询时：根据当前斜率 k = 2*prefix[i]，在队头找最优决策点

$$dp[i] = \min_{j < i} \{ dp[j] + (S_i - S_j)^2 \} + C$$

$$\text{整理为：} dp[i] = \min_{j < i} \{ (dp[j] + S_j^2) - 2S_i \cdot S_j \} + S_i^2 + C$$

📊 复杂度分析

💻 参考实现（C++）

#include 
using namespace std;
using ll = long long;

// 斜率优化 DP（以"任务安排"为例）
// dp[i] = min(dp[j] + (sum[i] - sum[j])^2 + C)
const int N = 50005;
ll sum[N], dp[N];
int q[N]; // 单调队列（存下标）

ll X(int j) { return sum[j]; }
ll Y(int j) { return dp[j] + sum[j] * sum[j]; }

// 判断 j1, j2, j3 是否满足下凸壳（斜率递增）
// (Y2-Y1)/(X2-X1) <= (Y3-Y2)/(X3-X2)
bool check(int j1, int j2, int j3) {
    return (Y(j2) - Y(j1)) * (X(j3) - X(j2)) <= (Y(j3) - Y(j2)) * (X(j2) - X(j1));
}

// 判断 j1 是否比 j2 更优（针对当前斜率 k）
// (Y2-Y1)/(X2-X1) >= k = 2*sum[i]
bool better(int j1, int j2, ll k) {
    return (Y(j2) - Y(j1)) <= k * (X(j2) - X(j1));
}

int main() {
    int n; ll C;
    cin >> n >> C;
    for (int i = 1; i <= n; i++) {
        cin >> sum[i];
        sum[i] += sum[i-1];
    }
    
    int l = 0, r = 0;
    q[r++] = 0; // dp[0] = 0
    for (int i = 1; i <= n; i++) {
        // 队头找最优
        while (r - l > 1 && better(q[l], q[l+1], 2 * sum[i])) l++;
        int j = q[l];
        dp[i] = dp[j] + (sum[i] - sum[j]) * (sum[i] - sum[j]) + C;
        
        // 新点入队，维护凸包
        while (r - l > 1 && check(q[r-2], q[r-1], i)) r--;
        q[r++] = i;
    }
    cout << dp[n] << endl;
    return 0;
}

⚠️ 常见坑点

📚 相关题目