动态规划的斜率优化 - NOI提高级教程

📖 算法原理：直线截距式与凸壳过滤

对于形式如 $dp[i] = \min \{ dp[j] + (s[i] - s[j])^2 \}$ 的 DP 方程，朴素转移为 $O(N^2)$。当决策点含有 $i$ 与 $j$ 的乘积项时，可将其化归为 解析几何直线斜截式。

📐 斜率优化几何映射定理

我们将只含 $j$ 的项设为 $y$ 和 $x$，含 $i$ 且与 $j$ 相乘的项设为斜率 $k$。方程化归为：

$$\color{cyan} y = k \cdot x + b$$

其中，$b$ 包含待求状态 $dp[i]$（例如 $b = dp[i] - s[i]^2$）。要使得 $dp[i]$ 最小，等价于寻找一个已知斜率 $k$ 的直线，在穿过决策点集中的某个点 $(x_j, y_j)$ 时，在 $Y$ 轴上的截距 $b$ 达到最小。

下凸壳 (Lower Convex Hull)：几何上，最优的决策点 $j$ 必然位于这群散点最下方的“下凸边缘”上。非凸壳上的内部点永远不可能成为最优解。
单调队列维护：
1. 头部出队（切线旋转）：随着 $i$ 增加，斜率 $k$ 单调递增。我们检查队列头部相邻两点的斜率，若 `slope(head, head+1) < k`，说明头部已经太缓，直接出队，让 `head+1` 成为切点。
2. 尾部出队（维护凸壳）：插入新点 $i$ 时，若它与队列尾部构成的斜率小于尾部原有的斜率（形成凹陷），说明原有尾部点已被包在内部，直接踢出队列。

演示速度：

点击"开始斜率递推"或"单步执行"观察单调队列如何通过旋转切线和裁剪尾部维护绿色下凸壳。

当前测试点 i-

当前切线斜率 K-

凸包队列 Queue[ ]

切线最优决策点-

double getSlope(int i, int j) {
    return (double)(y(j) - y(i)) / (x(j) - x(i));
}

void solve() {
    int head = 1, tail = 1;
    q[1] = 0; // 初始化单调队列
    
    for (int i = 1; i <= n; i++) {
        // 1. 头部出队：斜率单调递增，剔除切点左侧的不优元素
        while (head < tail && getSlope(q[head], q[head+1]) < 2 * s[i]) {
            head++;
        }
        
        int best_j = q[head]; // 2. 队首即为当前斜率下的最优决策点！
        dp[i] = dp[best_j] + (s[i] - s[best_j])^2;
        
        // 3. 尾部出队：新决策点入队，剔除违反下凸壳性质的凹陷元素
        while (head < tail && getSlope(q[tail-1], q[tail]) > getSlope(q[tail], i)) {
            tail--;
        }
        q[++tail] = i; // 4. 新决策点入队
    }
}

📋 斜率递推凸包维护日志