斜率优化DP中凸包维护的本质是用单调队列模拟下凸壳点集，使每次按斜率查询截距最优点的时间降至O(1)；核心前提是状态转移可化为f[i]=min{f[j]+A[i]·B[j]+C[i]}且B[j]单调递增。
斜率优化DP中凸包维护的本质是什么
斜率优化DP里所谓“维护凸包”，不是真去建几何凸包，而是用单调队列模拟下凸壳（或上凸壳）的点集，使得每次查询给定斜率 k 对应的最优决策点时，能在 O(1) 或 O(log n) 内拿到截距最小（或最大）的点。关键在于：状态转移方程必须能整理成 f[i] = min{ f[j] + A[i] * B[j] + C[i] } 形式，且 B[j] 单调递增（常见是 j 本身或前缀和数组），才能用单调队列维护。
单调队列怎么维护下凸壳的点对
假设你已将每个决策点 j 映射为二维平面上的点 (x_j, y_j) = (B[j], f[j])，目标是对于当前斜率 k_i = -A[i]，找使 y_j + k_i * x_j 最小的 j。这等价于在点集中找斜率为 -k_i 的直线与所有点连线中截距最小的那个点——即下凸壳上满足“相邻三点叉积非负”的点序列。
- 入队前检查队尾三点是否构成“上凸”：若
(x[r-1], y[r-1])、(x[r], y[r])、(x[new], y[new])满足叉积(x[r] - x[r-1]) * (y[new] - y[r]) - (y[r] - y[r-1]) * (x[new] - x[r]) ，则删掉 <code>r - 队首弹出条件不是看斜率大小，而是看队首两点连线斜率是否 ≤ 当前
k_i：若(y[1] - y[0]) / (x[1] - x[0]) ，说明 <code>0已永远不如1优，弹出 - 所有坐标和斜率计算中，
x[j]必须严格递增，否则除零或叉积符号失效；常见错误是没保证B[j]单调，导致队列退化为线性扫描
当斜率不单调时为什么单调队列失效
单调队列能 O(1) 弹出队首，前提是查询斜率 k_i 单调（如递增）。一旦 k_i 杂乱无章，队首“过期”点无法按序淘汰——你不能确定下一个 k_{i+1} 是比 k_i 大还是小，也就无法预判哪个点会重新变优。此时必须换李超树或二分凸包，但代价是 O(log n) 查询。
C++ Code Review Master
下载
组合式C++代码评审方案，融合静态分析、AI推理、多轮迭代评审和C++专项检查，适用于PR审查、增量代码审查、全项目评审和代码质量评分，触发词包括review cpp、cpp代码评审、C++review、代码审查。
- 典型反例：状态转移含
dp[i] = max{ dp[j] + a[i] * b[j] }，而a[i]无序 →k_i = -a[i]无序 → 单调队列退化 - 强行硬套单调队列会导致漏掉最优解，现象是答案偏大（求最小值时）或偏小（求最大值时），且调试时难以定位——因为逻辑上“看起来”每步都弹出了劣解
- 验证方法：打印所有入队
j对应的x[j]和查询时的k_i，确认二者是否各自单调
实际写代码时最容易错的三个地方
不是推错斜率公式，而是边界和类型处理翻车：
立即学习“C++免费学习笔记（深入）”；
- 叉积计算用
long long，但输入的f[j]和B[j]是int？乘法中间结果可能溢出，尤其n > 1e5时 —— 必须统一转long long再算 - 判断队首斜率时写成
(y[1]-y[0]) ，看似避开了除法，但若 <code>x[1]==x[0]（理论上不该发生，但初始化错就真会发生），直接崩溃；更安全的是用叉积形式重写比较逻辑 - 更新
dp[i]后立即把点(B[i], f[i])入队，但忘了此时B[i]必须 > 队尾x[r]—— 若相等，新点纵坐标更优也得替换，否则凸壳不合法
真正难的从来不是“怎么推公式”，而是确保单调性成立、数值不溢出、边界不越界这三件事同时成立。少一个，整个优化就回退到 O(n²)。
