动态规划斜率优化：从暴力O(n²)到O(n)的几何降维打击-平芜编程栈

1. 从“暴力”到“优雅”：斜率优化的核心动机

如果你刷过一些动态规划的题目，尤其是那些状态转移方程里带着(i - j) * (i - j)或者(a[i] - b[j])^2这类项，然后需要你求一个序列上的最优分割点j的问题，你大概率会写出一个 O(n²) 的算法。然后一看数据范围，n 是 10⁵ 甚至 10⁶，直接超时。这时候，你可能会想，有没有办法把内层循环的 O(n) 优化掉，变成 O(1) 或者 O(log n) 的决策？斜率优化（Slope Optimization）就是为了解决这类问题而生的。

我第一次遇到这类问题是在做“任务安排”类的题目时，状态转移方程大概是dp[i] = min{ dp[j] + (sumT[i] + S) * (sumC[i] - sumC[j]) }，其中sumT和sumC是前缀和。最直观的想法就是遍历所有j < i，取最小值。当 n 很大时，这显然不可行。斜率优化的本质，是把原本需要遍历比较的决策过程，转化成一个在平面上维护凸包（Convex Hull），并通过比较斜率来快速剔除劣质决策点的几何问题。听起来有点抽象，但它的核心思想非常直观：在众多候选决策中，有些决策是永远不可能成为最优解的，我们可以提前把它们淘汰掉。

为什么叫“斜率优化”？因为在转化后的几何模型里，判断一个决策点是否优于另一个决策点，关键在于比较两条直线的斜率。这个技巧能将许多形如dp[i] = min{ dp[j] + f(i) * g(j) + h(i) + k(j) }的方程优化到 O(n) 或 O(n log n)。它不像单调队列优化那样有固定的“窗口”概念，而是通过维护决策点的“凸性”来保证高效性。掌握它，相当于在 DP 优化武器库里增加了一件重型装备。

2. 从代数到几何：斜率优化的数学模型建立

要理解斜率优化，我们必须先完成一次关键的思维转换：将状态转移方程从纯粹的代数比较，转化为几何图形上的点与线。

我们以一个经典模型为例，假设状态转移方程为：dp[i] = min{ dp[j] + a[i] * b[j] }，其中j < i，且a[i]是随i单调递增的（这是应用斜率优化的常见前提之一）。对于固定的i，a[i]是常数。我们把min去掉，把方程改写为：dp[i] = dp[j] + a[i] * b[j]。

这可以进一步变形为：dp[j] = (-a[i]) * b[j] + dp[i]。

现在，请你盯着这个式子看：dp[j] = (-a[i]) * b[j] + dp[i]。它像什么？它是一条直线的方程！在这个方程里：

自变量x：是b[j]。
因变量y：是dp[j]。
斜率k：是-a[i]。
截距b：是dp[i]。

这意味着，对于每一个已经计算出来的决策点j，我们可以在平面直角坐标系上画出一个点P_j: (b[j], dp[j])。而我们当前要计算的dp[i]，实际上是在寻找一条斜率为k_i = -a[i]的直线，穿过某个已知点P_j后，得到的截距最小的那条直线。因为截距dp[i]正是我们要最小化的目标。

所以，整个动态规划的过程，就变成了：

每计算出一个dp[j]，就在坐标系里添加一个点(b[j], dp[j])。
当要计算dp[i]时，我们已知斜率k_i = -a[i]。我们需要从已有的所有点中，找到那个能让穿过它的、斜率为k_i的直线截距最小的点。

如果还是觉得抽象，我们可以代入具体数字。假设已有三个决策点： P1: (b[1]=2, dp[1]=5) P2: (b[2]=4, dp[2]=7) P3: (b[3]=6, dp[3]=6)

现在要计算i=4，且a[4]=3，即斜率k = -3。我们画三条斜率都为 -3 的直线，分别穿过 P1, P2, P3：

过 P1 的直线：y = -3*(x-2) + 5=> 截距dp[i] = 5 + 6 = 11
过 P2 的直线：y = -3*(x-4) + 7=> 截距dp[i] = 7 + 12 = 19
过 P3 的直线：y = -3*(x-6) + 6=> 截距dp[i] = 6 + 18 = 24

显然，过 P1 的直线截距最小，所以最优决策j=1，dp[4]=11。这个过程如果暴力做，就是 O(n)。但几何给了我们更快的视角。

2.1 凸包与最优决策点

关键问题来了：是不是所有点都有可能成为最优决策点？答案是否定的。有些点被其他点“完全包围”，在任何斜率下都不会成为最优。我们需要维护一个点集，使得其中的点在几何上构成一个“下凸壳”（Lower Convex Hull）。

什么是下凸壳？想象我们用一根橡皮筋从下方套住所有点，橡皮筋最终接触到的那些点连成的折线，就是下凸壳。对于寻找最小截距（当斜率k单调时），我们关心的是下凸壳。

如何判断一个点是否应该留在凸壳中？假设我们按x坐标（即b[j]）递增的顺序加入新点。维护一个点队列。当加入新点P_new时，我们检查队列末尾的两个点P_{k-1}和P_k与P_new的关系。如果P_k在P_{k-1}到P_new的连线上方，那么P_k就是一个“凸点”，应该保留；如果P_k在连线下方或线上，那么P_k对于构成下凸壳是无效的，应该被弹出队列。这个判断可以通过计算叉积（Cross Product）或者比较斜率来完成。

更常用的判断方法是比较斜率。设队列末尾两点为(x1, y1),(x2, y2)，新点为(x3, y3)。当(y2 - y1) / (x2 - x1) >= (y3 - y2) / (x3 - x2)时，说明P2不在下凸壳上，需要弹出。为了避免除法精度问题，通常写成乘法形式：(y2 - y1) * (x3 - x2) >= (y3 - y2) * (x2 - x1)。注意，这里>=对应维护下凸壳（求最小截距），如果要求最大截距，则维护上凸壳，判断条件为<=。

2.2 斜率单调性下的决策剔除

建立了凸包后，我们如何快速找到对于当前斜率k_i的最优决策点？如果查询的斜率k_i是单调的（例如本题假设a[i]单调增，则k_i = -a[i]单调减），那么最优决策点在凸壳上也是单调移动的。

具体来说，我们维护一个决策指针（或直接操作队列头部）。对于下凸壳和单调递减的斜率k，最优决策点j是使得穿过P_j和P_{j+1}的直线斜率第一个小于等于当前斜率k_i的那个点j。因为斜率更小的直线更“平缓”，在当前斜率下能给出更小的截距。

判断条件：设队列头部的两点为P_j (x_j, y_j)和P_{j+1} (x_{j+1}, y_{j+1})。如果(y_{j+1} - y_j) / (x_{j+1} - x_j) <= k_i，那么对于斜率k_i来说，P_{j+1}比P_j更优（或一样优），因此我们可以将P_j从队列头部弹出。一直弹到上述不等式不成立为止，此时队列头部的点就是最优决策点。

同样，使用乘法形式避免除法：(y_{j+1} - y_j) <= k_i * (x_{j+1} - x_j)。

为什么？从几何上理解：(y_{j+1} - y_j) / (x_{j+1} - x_j)是凸壳上相邻两点连线的斜率。如果这个斜率小于等于我们手中的直线斜率k_i，说明凸壳在P_j处比我们的直线更“平”。我们要找的是凸壳上第一个斜率大于等于k_i的线段左侧的点（对于下凸壳求最小截距）。当k_i单调递减时，这个最优决策点只会向右移动，不会向左，所以可以单调队列维护。

3. 经典例题实战：任务安排（洛谷P2365 / AcWing 301）

理论讲了很多，我们用一个最经典的题目来串起整个流程。题目大意：有 N 个任务排成序列，每个任务有完成所需时间T_i和费用系数C_i。执行一批任务前，需要启动时间 S。执行一批任务[j+1, i]的费用为这批任务的完成时刻（启动时间+这批任务总时间）乘以这批任务费用系数之和。目标是最小化总费用。

我们定义：

sumT[i]为时间的前缀和。
sumC[i]为费用系数的前缀和。
dp[i]表示处理完前i个任务的最小费用。

状态转移：考虑最后一批任务是从j+1到i。那么dp[i] = min{ dp[j] + (S * (sumC[N] - sumC[j]) + (sumT[i] - sumT[j]) * (sumC[i] - sumC[j]) }。这里S * (sumC[N] - sumC[j])是启动时间对后续所有任务（包括i之后的）产生的额外费用，这是一个经典的费用提前计算思想。

为了简化，我们令st[i] = sumT[i],sc[i] = sumC[i]。方程写为：dp[i] = min{ dp[j] + S * (sc[N] - sc[j]) + (st[i] - st[j]) * (sc[i] - sc[j]) }，其中0 <= j < i。

展开并整理与j相关的项：dp[i] = min{ dp[j] + S*sc[N] - S*sc[j] + st[i]*sc[i] - st[i]*sc[j] - st[j]*sc[i] + st[j]*sc[j] }

对于固定的i，S*sc[N]和st[i]*sc[i]是常数，可以提到min外面。我们关注min里面的部分：dp[j] - S*sc[j] - st[i]*sc[j] - st[j]*sc[i] + st[j]*sc[j]

这个式子看起来复杂，但我们可以尝试将其化为Y - k * X的形式。把只与j有关的项视为Y，把同时与i和j有关的乘积项拆开，让其中一个因子作为斜率k。

观察- st[i]*sc[j] - st[j]*sc[i] + st[j]*sc[j]。我们希望把st[i]或sc[i]提出来作为斜率。通常选择那个单调的变量作为斜率。这里st[i]和sc[i]都是单调递增的（因为时间和费用系数均为正）。我们选择st[i]作为斜率k。

重新组合与j有关的项：令：Y(j) = dp[j] - S*sc[j] + st[j]*sc[j]X(j) = sc[j]

那么min里面的式子可以写为：Y(j) - st[i] * X(j) - st[j]*sc[i]。

糟糕，这里多出了一个- st[j]*sc[i]，它无法融入Y(j) - k*X(j)的形式，因为st[j]和sc[i]都是变量。这说明我们最初的方程形式不够“标准”。我们需要更严格的“斜率优化”标准形式。

让我们回到原始方程，并采用更常见的费用提前计算的写法：dp[i] = min{ dp[j] + st[i] * (sc[i] - sc[j]) + S * (sc[N] - sc[j]) }。这里S*(sc[N]-sc[j])是j之后所有任务（包括i）因这次启动多付的费用。

将常数项S*sc[N]提出：dp[i] = min{ dp[j] - (S + st[i]) * sc[j] } + st[i]*sc[i] + S*sc[N]

现在，对于固定的i，令k_i = S + st[i]（单调递增），b[j] = sc[j]（单调递增）。那么min里面的部分就是dp[j] - k_i * b[j]。

这等价于求min{ dp[j] - k_i * b[j] }。我们把它写成直线截距的形式：dp[j] = k_i * b[j] + B，其中B就是dp[i]减去常数项的部分。为了最小化dp[i]，我们需要最小化截距B，即最大化-B。但更直观地，我们直接处理min{ dp[j] - k_i * b[j] }。

我们可以令y(j) = dp[j],x(j) = b[j] = sc[j]。那么问题转化为：给定一系列点(x(j), y(j))，和斜率k_i，找一条斜率为k_i的直线穿过某个点，使得该直线的截距y(j) - k_i * x(j)最小。

看，这就是我们第二节中推导出的标准形式！只不过这里的“截距”是y - kx，而之前是y = kx + b中的b。本质是一样的。

3.1 代码实现与逐行解析

假设我们已经预处理了st[i]和sc[i]。下面是核心的 DP 循环部分，使用单调队列维护下凸壳。

#include <iostream> #include <cstring> using namespace std; typedef long long LL; const int N = 300010; // 根据题目数据范围 int n, s; LL st[N], sc[N]; LL dp[N]; int q[N]; // 单调队列，存储决策点下标 j int main() { cin >> n >> s; for (int i = 1; i <= n; i++) { cin >> st[i] >> sc[i]; st[i] += st[i-1]; sc[i] += sc[i-1]; } int hh = 0, tt = 0; // 队列初始化，通常放入决策点 0 q[0] = 0; // dp[0] = 0 是一个合法的决策起点 for (int i = 1; i <= n; i++) { // 1. 维护队列头，找到最优决策点 j // 条件： (dp[q[hh+1]] - dp[q[hh]]) <= (s + st[i]) * (sc[q[hh+1]] - sc[q[hh]]) // 即斜率 (y2-y1)/(x2-x1) <= k_i while (hh < tt && (dp[q[hh+1]] - dp[q[hh]]) <= (s + st[i]) * (sc[q[hh+1]] - sc[q[hh]])) { hh++; // 弹出队头，因为 q[hh+1] 更优 } int j = q[hh]; // 最优决策点 // 2. 计算 dp[i] dp[i] = dp[j] + st[i] * (sc[i] - sc[j]) + s * (sc[n] - sc[j]); // 3. 将点 i 加入决策集合，维护凸壳 // 条件： (dp[i] - dp[q[tt]]) * (sc[q[tt]] - sc[q[tt-1]]) >= (dp[q[tt]] - dp[q[tt-1]]) * (sc[i] - sc[q[tt]]) // 即斜率 (y_i - y_tt) / (x_i - x_tt) >= (y_tt - y_{tt-1}) / (x_tt - x_{tt-1}) // 注意：这里比较的是加入 i 点后，队列末尾两点 (tt-1, tt) 的斜率是否小于等于新两点 (tt, i) 的斜率 // 乘法形式避免除法，注意 long long 防止溢出 while (hh < tt && (dp[i] - dp[q[tt]]) * (sc[q[tt]] - sc[q[tt-1]]) <= (dp[q[tt]] - dp[q[tt-1]]) * (sc[i] - sc[q[tt]])) { tt--; // 弹出队尾，不满足下凸性 } q[++tt] = i; // 加入新决策点 } cout << dp[n] << endl; return 0; }

逐行解析关键点：

初始化：q[0]=0。因为dp[0]=0，对应点(sc[0], dp[0]) = (0, 0)，这是一个合法的决策起点。
寻找最优决策点（队头维护）：
- while (hh < tt && (dp[q[hh+1]] - dp[q[hh]]) <= (s + st[i]) * (sc[q[hh+1]] - sc[q[hh]])
- 这个条件就是判断：(Y(q[hh+1]) - Y(q[hh])) / (X(q[hh+1]) - X(q[hh])) <= k_i。
- 其中Y(j)=dp[j],X(j)=sc[j],k_i = S + st[i]。
- 如果成立，说明点q[hh+1]比q[hh]更优（对于当前斜率k_i），所以弹出q[hh]。
- 循环结束后，q[hh]就是使得截距dp[j] - k_i * sc[j]最小的j。
状态转移：直接用找到的j计算dp[i]。
加入新点并维护凸壳（队尾维护）：
- while (hh < tt && (dp[i] - dp[q[tt]]) * (sc[q[tt]] - sc[q[tt-1]]) <= (dp[q[tt]] - dp[q[tt-1]]) * (sc[i] - sc[q[tt]])
- 这个条件判断的是：队列末尾三点q[tt-1],q[tt],i是否构成“上凸”？（注意，我们维护的是下凸壳，所以要剔除上凸的点）。
- 设三点为 A(q[tt-1]), B(q[tt]), C(i)。
- 向量 AB =(Xb-Xa, Yb-Ya)，向量 BC =(Xc-Xb, Yc-Yb)。
- 判断 AB 到 BC 是否“左转”（即叉积 >=0）。在斜率表示下，就是判断(Yb-Ya)/(Xb-Xa) <= (Yc-Yb)/(Xc-Xb)。如果成立，说明 B 点在上凸的位置，需要弹出。
- 我们代码里用的是<=，对应维护下凸壳（求最小值）。如果题目是求最大值，需要维护上凸壳，则这里的判断应改为>=。
- 乘法形式是为了避免除法带来的精度问题，但要注意乘法的方向，确保不等式等价。

一个极易出错的细节：在队尾维护的while循环判断中，不等号的方向与我们是求最小值还是最大值、以及X坐标（即sc[j]）是否单调递增密切相关。在本例中，sc[j]单调增，求最小值，维护下凸壳，使用<=。如果X坐标单调减，不等式方向可能需要调整。最稳妥的方法是画图，或者记住：维护下凸壳（求最小截距）时，相邻三点应满足斜率递增。如果新点i的加入导致末尾两点斜率大于等于新线段斜率（即斜率不再严格递增），则弹出队尾。

4. 斜率不单调与二分查找

前面讨论的情况基于一个关键假设：每次查询的斜率k_i是单调的。这样我们才能用单调队列在 O(1) 均摊时间内从队头弹出无用决策。但如果斜率k_i没有单调性呢？例如，状态转移方程中的a[i]不是单调的。

此时，我们无法再单调地移动队头指针来剔除决策点，因为对于不同的i，最优决策点j可能会在凸壳上来回移动。但是，我们依然可以维护一个完整的凸壳。因为点的横坐标X(j)（通常是b[j]）在按j递增的顺序加入时，往往是单调的（例如前缀和），所以凸壳可以用单调栈或双端队列在 O(n) 内维护好。

当需要计算dp[i]时，问题转化为：在一个静态的（或动态增长但已维护好的）凸壳上，找到一点P，使得过P点斜率为k_i的直线截距最小（或最大）。这是一个在凸壳上的查找问题。

对于下凸壳求最小截距，最优决策点P是凸壳上第一个使得其与后继点连线斜率大于等于k_i的点。因为斜率小于k_i的部分更平缓，在当前斜率下截距更大。由于凸壳上的斜率是单调递增的，我们可以使用二分查找来定位这个点。

具体实现时，我们仍然用队列q[]存储凸壳上的点下标。二分查找的check函数就是比较相邻两点的斜率与k_i的大小。设mid为候选点，我们需要判断K(q[mid], q[mid+1])与k_i的关系。

如果K(q[mid], q[mid+1]) >= k_i，说明mid点可能就是我们想要的点，或者最优点在mid左边，我们令r = mid。
如果K(q[mid], q[mid+1]) < k_i，说明mid点还不够“陡”，最优决策点应该在mid右边，令l = mid + 1。

最后，q[l]就是最优决策点。查找复杂度为 O(log n)，总复杂度为 O(n log n)。

4.1 代码示例：斜率不单调的情况

假设状态转移为dp[i] = min{ dp[j] + (a[i] - b[j])^2 }，其中a[i]无单调性，b[j]单调递增。

展开：dp[i] = min{ dp[j] + a[i]^2 - 2*a[i]*b[j] + b[j]^2 }。对于固定的i，a[i]^2是常数。所以等价于求min{ (dp[j] + b[j]^2) - 2*a[i]*b[j] }。

令：Y(j) = dp[j] + b[j]^2X(j) = b[j]k_i = 2 * a[i]

那么就是求min{ Y(j) - k_i * X(j) }。X(j)单调增，k_i无单调性。

我们需要维护一个关于点(X(j), Y(j))的下凸壳。由于X(j)单调增，凸壳可以在 O(n) 内用单调队列维护（队尾弹出不满足凸性的点）。但在查询时，我们需要二分查找凸壳。

// 假设已有预处理好的 b[] 和 a[] LL dp[N]; int q[N], hh, tt; // 计算斜率，注意使用 double 或 long double 防止精度问题，或者用乘法判断 double slope(int j1, int j2) { double dx = b[j2] - b[j1]; if (fabs(dx) < 1e-18) return ...; // 处理除零，通常 b[] 严格单调则不会 return ( (dp[j2] + b[j2]*b[j2]) - (dp[j1] + b[j1]*b[j1]) ) / dx; } // 在凸壳 q[hh..tt] 上二分查找最优决策点 int find_optimal(int i) { LL k = 2 * a[i]; int l = hh, r = tt; while (l < r) { int mid = (l + r) >> 1; // 如果 mid 和 mid+1 的斜率小于 k，说明 mid 还不够优，答案在右边 if (slope(q[mid], q[mid+1]) < k) { l = mid + 1; } else { r = mid; } } return q[l]; } for (int i = 1; i <= n; i++) { // 1. 二分查找最优决策点 int j = find_optimal(i); // 2. 状态转移 dp[i] = dp[j] + (a[i] - b[j]) * (a[i] - b[j]); // 或其他等价形式 // 3. 将 i 作为新决策点加入凸壳 // 维护队尾凸性：如果末尾三点不满足下凸，则弹出队尾 while (hh < tt) { // 判断 (tt-1, tt) 和 (tt, i) 的斜率 // 如果 slope(q[tt-1], q[tt]) >= slope(q[tt], i)，则弹出 q[tt] // 使用叉积或斜率比较，注意精度 if ( slope(q[tt-1], q[tt]) >= slope(q[tt], i) ) { tt--; } else { break; } } q[++tt] = i; }

重要提示：在二分查找中，我们比较的是斜率。如果X坐标差可能为 0，需要特判。在实际竞赛中，为了完全避免浮点数精度误差，通常会使用叉积进行判断，将除法比较转化为乘法比较。例如，判断slope(j1, j2) < k可以写为(Y2-Y1) < k * (X2-X1)。但在二分查找中，k是变化的，用乘法需要小心。一种更鲁棒的方法是在凸壳上二分查找第一个斜率大于等于k的线段，这个比较可以用叉积实现，但逻辑稍复杂。许多选手在精度要求不高时直接使用double，并设置一个较小的eps。

5. 边界条件、精度与实战心得

斜率优化虽然强大，但实现细节上的坑非常多，一不小心就会 WA（Wrong Answer）或者 TLE（Time Limit Exceeded）。

5.1 初始化与边界

决策点 0：绝大多数序列 DP 问题，dp[0]都是一个合法决策，代表从开头开始分组。一定要记得将其加入决策队列。对应的点坐标(X(0), Y(0))需要根据定义计算好。
队列初始状态：通常hh=0, tt=0，且q[0]=0。这意味着队列里有一个点。在队头弹出判断时，条件是while (hh < tt && ...)，确保队列中至少有两个点时才需要比较斜率。
横坐标相等：如果不同的决策点j对应的X(j)可能相等，那么在计算斜率时会出现除零错误。此时需要特殊处理。通常，如果X(j)相等，那么Y(j)更小的点更优（对于下凸壳求最小值），可以直接保留更优的那个点。在维护凸壳时，如果新点i的X(i)与队尾点X(q[tt])相等，则需要比较Y值，决定是替换队尾点还是直接跳过。

5.2 精度与比较方式

这是斜率优化最棘手的部分之一。

浮点数除法：直接使用double计算斜率(Y2-Y1)/(X2-X1)最简单，但可能有精度误差。在比较slope1 <= slope2时，如果两个斜率非常接近，浮点数比较可能出错。对于大多数题目，double的精度足够，但有些毒瘤数据会卡精度。
乘法判断：为了杜绝精度问题，通常将斜率比较(y2-y1)/(x2-x1) <= (y3-y2)/(x3-x2)转化为乘法形式：(y2-y1)*(x3-x2) <= (y3-y2)*(x2-x1)。但这里有一个巨大的坑：符号！
- 我们必须确保乘法的两边是同号的，或者处理好异号情况。
- 对于下凸壳，X坐标通常是单调递增的，所以(x2-x1)和(x3-x2)都是正数。此时，不等式两边同时乘以正数(x2-x1)*(x3-x2)，不等号方向不变。这是最安全的情况。
- 如果X坐标单调递减，那么(x2-x1)和(x3-x2)都是负数，乘积为正数，不等号方向也不变。
- 但是，如果X坐标不是单调的（在二分查找凸壳时，我们维护的凸壳点X坐标是单调的，但查询斜率k_i可能使得比较slope(j, j+1) <= k_i时，k_i可能为负，且(x_{j+1}-x_j)为正），直接乘(x_{j+1}-x_j)是正数，没问题。但如果k_i是表达式，且(x_{j+1}-x_j)可能为负（在非单调X的凸壳二分中不会，因为凸壳点X有序），就需要分类讨论。
- 最佳实践：在X坐标单调的前提下，一律使用乘法判断。确保你清楚X的单调性，以及你维护的是上凸壳还是下凸壳，从而决定不等号方向。
溢出问题：(y2-y1)*(x3-x2)这类乘法，y和x常常是long long范围，乘积可能溢出 64 位整数。在 C++ 中，可以使用__int128或者转化为long double进行比较。例如：
```
bool check(int j1, int j2, int i) { long double left = (long double)(Y(j2)-Y(j1)) * (X(i)-X(j2)); long double right = (long double)(Y(i)-Y(j2)) * (X(j2)-X(j1)); // 对于下凸壳维护，如果 left <= right 则弹出 j2 return left <= right; }
```
使用long double比较可以避免溢出，但仍有极小的精度风险。

5.3 决策单调性与四边形不等式

斜率优化是决策单调性的一种特殊情况。决策单调性是指，对于状态i，其最优决策点opt[i]随着i增大而单调不减（或单调不增）。斜率优化问题中，如果斜率k_i和横坐标X(j)都单调，那么决策点opt[i]是单调的，这对应了可以用单调队列维护队头。

更一般的决策单调性，可以用分治或者单调栈+二分的方法解决，适用范围比斜率优化更广。而四边形不等式是证明决策单调性的有力工具。对于斜率优化题目，我们通常不需要显式地证明四边形不等式，只要能把方程化成Y - kX的形式，并且X和k有单调性，就可以套用模板。

5.4 调试技巧

打印决策队列：在 DP 循环中，打印出每个i对应的队列状态q[hh..tt]，以及计算出的最优决策j。观察决策点是否单调移动，凸壳点坐标是否合理。
小数据暴力对拍：写一个 O(n²) 的暴力 DP，与斜率优化版本对拍。生成随机小数据（n<=1000），比较两个程序的dp[n]是否一致。这是最有效的查错方法。
检查不等式方向：如果答案不对，首先怀疑队尾维护凸壳的不等式方向是否写反。可以画三个点，手动计算一下，看看是应该用<=还是>=。记住口诀：下凸壳（求最小值）斜率递增，维护时踢掉队尾斜率大于等于新线段斜率的点；上凸壳（求最大值）斜率递减，维护时踢掉队尾斜率小于等于新线段斜率的点。但最靠谱的还是画图。
检查初始化：确认dp[0]的值是否正确，以及点(X(0), Y(0))是否已入队。
检查溢出和精度：对于乘法判断，使用long double或__int128来避免溢出。对于浮点数比较，使用eps（如1e-18）。

斜率优化是一个“会者不难，难者不会”的算法。它的核心在于建模——将代数问题转化为几何问题。一旦转化成功，剩下的就是套用维护凸壳和查找最优点的模板。多练习几道经典题目（如任务安排、玩具装箱、土地购买、仓库建设等），熟悉各种变形，就能逐渐掌握这项强大的优化技术。记住，关键步骤永远是：1) 化简方程，分离i和j；2) 确定X(j),Y(j),k_i；3) 判断X和k的单调性；4) 选择单调队列或二分凸壳；5) 小心实现，注意精度和边界。