Codeforces 斜率优化与 Slope Trick 题解两则：CF311B 与 CF713C

凸性与动态规划转移降维

一维与二维动态规划中，当状态转移方程包含与决策变量和状态变量同时耦合的交叉项，或者状态本身关于自变量呈分段线性凸性时，直接枚举决策往往会带来 $O(n^2)$ 甚至更高的时间复杂度。利用代价函数的凸性，两类最常见的降维手段分别是：

斜率优化（Convex Hull Trick, CHT）：将转移改写为直线簇 $y = kx + b$ 的极值查询或点积查询，通过单调队列或李超线段树维护下（上）凸壳。
Slope Trick：当整张 DP 表 $f_i(x)$ 关于连续或离散自变量 $x$ 为分段线性凸函数（Piecewise Linear Convex Function）时，不显式离散化 $x$ ，而是直接用优先队列维护斜率变化拐点集合。

下文分别以 Codeforces 311B（Div. 1 B, 2400）与 Codeforces 713C（Div. 1 C, 2300）为例给出完整推导与实现。

CF311B Cats Transport：前缀转化与单调队列斜率优化

题目抽象

山脚为 $1$ 号山丘，共有 $n$ 座山丘，相邻山丘间距给定，可预处理出 $1$ 号山丘到第 $k$ 座山丘的距离 $D_k$ （ $D_1 = 0$ ）。共有 $m$ 只猫，第 $i$ 只猫在山丘 $H_i$ 玩耍至时刻 $T_i$ 。

现有 $p$ 名饲养员从 $1$ 号山丘出发，各自选择一个出发时刻 $s \ge 0$ ，以单位速度向编号增大的方向匀速行走（经过山丘 $k$ 的时刻为 $s + D_k$ ），沿途接走所有满足 $T_i \le s + D_{H_i}$ 且尚未被接走的猫。求所有猫等待时间之和的最小值。

数据范围： $n, m \le 10^5$ ， $p \le 100$ ， $T_i \le 10^9$ 。

独立化每只猫的出发下界

若饲养员在时刻 $s$ 从 $1$ 号山丘出发，他到达山丘 $H_i$ 的时刻为 $s + D_{H_i}$ 。能接走第 $i$ 只猫当且仅当：

s + D_{H_i} \ge T_i \iff s \ge T_i - D_{H_i}

定义每只猫的特征阈值：

A_i = T_i - D_{H_i}

此时该猫的等待时间恰为：

(s + D_{H_i}) - T_i = s - A_i

至此，山丘坐标 $D_{H_i}$ 已完全消去。问题等价于：数轴上有 $m$ 个点 $A_1, A_2, \dots, A_m$ ，选定 $p$ 个锚点 $s_1, s_2, \dots, s_p$ ，每个点 $A_i$ 归属某个满足 $s_k \ge A_i$ 的锚点，代价为 $s_k - A_i$ ，求最小总代价。

将 $A_1 \le A_2 \le \dots \le A_m$ 升序排序后，任意一名饲养员负责的猫必然构成排序后的一段连续区间 $[j+1, i]$ ，且最优出发时刻必取区间右端点 $s = A_i$ 。设前缀和 $S_i = \sum_{r=1}^{i} A_r$ ，则区间 $[j+1, i]$ 的等待代价为：

\operatorname{cost}(j+1, i) = \sum_{r=j+1}^{i} (A_i - A_r) = (i - j) A_i - (S_i - S_j)

转移方程与凸壳展开

设 $f(k, i)$ 表示前 $k$ 名饲养员接走前 $i$ 只猫的最小等待时间，转移为：

f(k, i) = \min_{0 \le j < i} \left\{ f(k-1, j) + (i - j) A_i - (S_i - S_j) \right\}

固定层数 $k$ ，将只与 $i$ 相关的项移出 $\min$ ，并将 $j$ 相关项整理为一次函数形式：

f(k, i) - i A_i + S_i = \min_{0 \le j < i} \left\{ -A_i \cdot j + \bigl(f(k-1, j) + S_j\bigr) \right\}

对每个决策 $j$ ，将其视为平面上的点 $(x_j, y_j)$ ：

x_j = j, \qquad y_j = f(k-1, j) + S_j

若两个决策 $j_1 < j_2$ 中 $j_2$ 优于或等于 $j_1$ ，则：

-A_i x_{j_2} + y_{j_2} \le -A_i x_{j_1} + y_{j_1} \iff \frac{y_{j_2} - y_{j_1}}{x_{j_2} - x_{j_1}} \le A_i

由于横坐标 $x_j = j$ 严格递增，且排序后查询斜率 $A_i$ 单调不降，可以用双端队列维护点集 $(x_j, y_j)$ 的下凸壳：

队首弹出：若队首前两个点 $q_0, q_1$ 满足斜率 $\operatorname{slope}(q_0, q_1) \le A_i$ ，因后续 $A_{i'} \ge A_i$ ， $q_0$ 永远不可能再成为最优决策，弹出 $q_0$ 。
转移取值：此时队首 $q_0$ 即为状态 $i$ 的最优决策。
队尾维护凸性：加入新决策点 $p = (x_i, y_i)$ 前，若队尾两点 $q_{r-1}, q_r$ 与 $p$ 满足 $\operatorname{slope}(q_{r-1}, q_r) \ge \operatorname{slope}(q_r, p)$ ，说明 $q_r$ 位于上凸折点，弹出 $q_r$ 。

为避免浮点精度损失，斜率比较统一改写为交叉相乘（使用 __int128 防止溢出）：

\frac{y_b - y_a}{x_b - x_a} \le \frac{y_c - y_b}{x_c - x_b} \iff (y_b - y_a)(x_c - x_b) \le (y_c - y_b)(x_b - x_a)

C++ 实现

每个状态在每层入队、出队各一次，单层复杂度 $O(m)$ ，总时间复杂度 $O(m \log m + pm)$ ，空间复杂度可滚动压缩至 $O(m)$ 。

#include <algorithm>
#include <iostream>
#include <vector>

using i64 = long long;
using i128 = __int128_t;

constexpr i64 INF = 1LL << 60;

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int n, m, p;
    if (!(std::cin >> n >> m >> p)) return 0;

    std::vector<i64> d(n + 1, 0);
    for (int i = 2; i <= n; ++i) {
        i64 dist;
        std::cin >> dist;
        d[i] = d[i - 1] + dist;
    }

    std::vector<i64> a(m + 1, 0);
    for (int i = 1; i <= m; ++i) {
        int h;
        i64 t;
        std::cin >> h >> t;
        a[i] = t - d[h];
    }

    std::sort(a.begin() + 1, a.end());

    std::vector<i64> s(m + 1, 0);
    for (int i = 1; i <= m; ++i) {
        s[i] = s[i - 1] + a[i];
    }

    p = std::min(p, m);
    std::vector<i64> dp_prev(m + 1, INF), dp_cur(m + 1, INF);
    dp_prev[0] = 0;

    std::vector<int> q(m + 1);

    for (int k = 1; k <= p; ++k) {
        auto y = [&](int j) -> i64 { return dp_prev[j] + s[j]; };

        int head = 0, tail = 0;
        q[tail++] = 0;
        dp_cur[0] = 0;

        for (int i = 1; i <= m; ++i) {
            while (tail - head >= 2) {
                int j1 = q[head], j2 = q[head + 1];
                if (y(j2) - y(j1) <= a[i] * (j2 - j1)) {
                    ++head;
                } else {
                    break;
                }
            }
            int best = q[head];
            dp_cur[i] = dp_prev[best] + (i - best) * a[i] - (s[i] - s[best]);

            if (dp_prev[i] >= INF / 2) continue;
            while (tail - head >= 2) {
                int j1 = q[tail - 2], j2 = q[tail - 1];
                i128 lhs = static_cast<i128>(y(j2) - y(j1)) * (i - j2);
                i128 rhs = static_cast<i128>(y(i) - y(j2)) * (j2 - j1);
                if (lhs >= rhs) {
                    --tail;
                } else {
                    break;
                }
            }
            q[tail++] = i;
        }
        dp_prev.swap(dp_cur);
    }

    std::cout << dp_prev[m] << '\n';
    return 0;
}

CF713C Sonya and Problem Wihtout a Legend：Slope Trick

题目抽象与非严格化变换

给定长度为 $n$ （ $n \le 3000$ ，加强版可达 $n \le 3 \times 10^5$ ）的整数序列 $a_1, a_2, \dots, a_n$ 。每次操作可以将任意元素加 $1$ 或减 $1$ ，求将序列变为严格递增整数序列 $b_1 < b_2 < \dots < b_n$ 所需的最小操作次数：

\min_{b_1 < b_2 < \dots < b_n} \sum_{i=1}^{n} |a_i - b_i|

因为 $b_i \in \mathbb{Z}$ ，严格不等式 $b_{i-1} < b_i$ 等价于 $b_{i-1} \le b_i - 1$ ，进而等价于：

b_1 - 1 \le b_2 - 2 \le \dots \le b_n - n

令 $a'_i = a_i - i$ ， $x_i = b_i - i$ ，原问题转化为求非严格递增序列 $x_1 \le x_2 \le \dots \le x_n$ ，使得：

\min_{x_1 \le x_2 \le \dots \le x_n} \sum_{i=1}^{n} |x_i - a'_i|

下文为书写简洁，将变换后的 $a'_i$ 仍记作 $a_i$ 。

分段线性凸函数的递推性质

定义 $f_i(x)$ 为考虑前 $i$ 个位置且 $x_i = x$ 时的最小代价，并定义前缀最小值函数 $g_i(x) = \min_{y \le x} f_i(y)$ 。递推关系为：

f_i(x) = g_{i-1}(x) + |x - a_i|, \qquad g_i(x) = \min_{y \le x} f_i(y)

可以通过归纳法证明： $f_i(x)$ 与 $g_i(x)$ 均为关于 $x$ 的分段线性凸函数，且每段的斜率均为整数。

取前缀最小值算子 $g_i(x) = \min_{y \le x} f_i(y)$ ：设 $f_i(x)$ 在 $x = x^*$ 处取得全局最小值（即左侧斜率 $\le 0$ ，右侧斜率 $> 0$ ）。对于 $x \ge x^*$ ，有 $g_i(x) = f_i(x^*)$ ，即将 $x^*$ 右侧所有大于 $0$ 的斜率全部截断为 $0$ ，左侧保持不变。
叠加绝对值函数 $+|x - a_i|$ ：函数 |x−ai||x - a_i| 在 x<aix < a_i 处斜率为 −1-1，在 x>aix > a_i 处斜率为 +1+1。与 gi−1(x)g_{i-1}(x) 相加后：
- 区间 $(-\infty, a_i)$ 上的斜率全部减 $1$ ；
- 区间 $(a_i, +\infty)$ 上的斜率全部加 $1$ ；
- 这等价于在拐点多重集（斜率每变化 $+1$ 记入一个拐点）中插入两个 $a_i$ 。

用大根堆维护左侧拐点集

设 $g_{i-1}(x)$ 在 $(-\infty, +\infty)$ 上的左端渐近斜率为 $-i+1$ ，右端斜率为 $0$ ，因此它恰好由 $i-1$ 个斜率变化拐点 $p_1 \le p_2 \le \dots \le p_{i-1}$ 唯一确定（每经过一个拐点 $p_k$ ，斜率增加 $1$ ），其中最大值 $p_{i-1}$ 即为斜率变为 $0$ 的左端点。

在第 $i$ 步加入 $|x - a_i|$ 并过渡到 $g_i(x)$ 时：

向拐点多重集 $Q$ 中加入两个 $a_i$ 。此时 $f_i(x)$ 的最右端斜率由 $0$ 变为 $+1$ 。
为得到 $g_i(x) = \min_{y \le x} f_i(y)$ ，需要抹平最右侧斜率为 $+1$ 的射线，即弹出多重集 $Q$ 中的最大元素 $p_{\max}$ 。
若刚才加入的 $a_i < p_{\max}$ ，则最小值函数值增加了 $p_{\max} - a_i$ ；若 $a_i \ge p_{\max}$ ，则加入两个 $a_i$ 再弹出一个 $a_i$ ，最小值不变。

整个过程只需一个大根堆 std::priority_queue<long long>，每次压入两次 $a_i$ 、弹出一次堆顶并累加代价差 q.top() - a[i]，时间复杂度从 $O(n^2)$ 降至 $O(n \log n)$ 。

#include <iostream>
#include <queue>

using i64 = long long;

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int n;
    if (!(std::cin >> n)) return 0;

    std::priority_queue<i64> pq;
    i64 ans = 0;

    for (int i = 1; i <= n; ++i) {
        i64 a;
        std::cin >> a;
        a -= i;

        pq.push(a);
        pq.push(a);
        ans += pq.top() - a;
        pq.pop();
    }

    std::cout << ans << '\n';
    return 0;
}

构造最优序列 $b_i$

若题目同时要求输出最优序列（如洛谷 P4331），只需记录每一步求得 $g_i(x)$ 时最右侧斜率为 $0$ 的左端点 $\operatorname{opt}_i = \max Q$ ，最后从后向前做一次后缀截断：

x_n = \operatorname{opt}_n, \qquad x_i = \min(x_{i+1}, \operatorname{opt}_i), \qquad b_i = x_i + i

这是因为 $g_i(x)$ 在 $[\operatorname{opt}_i, +\infty)$ 上导数为 $0$ ，而在 $\operatorname{opt}_i$ 左侧严格递减，因此在满足 $x_i \le x_{i+1}$ 的约束下取 $\min(x_{i+1}, \operatorname{opt}_i)$ 必然同时达到每一步的下界。