跳台阶

GitHub跳转原题关系图返回列表

把台阶分给两条从地面出发的链,代价是各链绝对差之和;用「一条链停在 H_i、另一条停在 x」的 DP 加锥形下包络,两棵树状数组维护前缀最小做到 O(n log n)。

OJ: roj

题目 ID: 1744

难度:提高+/省选-

标签:动态规划树状数组数据结构python

创建: 2026-10-07 21:59

更新: 2026-10-07 21:59

形式化题目

有 NN 个台阶排成一行,第 ii 个台阶高度 HiH_i(0<Hi⩽1090 < H_i \leqslant 10^9),地面高度 H0=0H_0 = 0。 把台阶编号集合 {1,2,…,N}\{1, 2, \dots, N\} 分成两个子集 Sa,SbS_a, S_b(可以为空), 对 S={P1<P2<⋯<P∣S∣}S = \{P_1 < P_2 < \dots < P_{|S|}\} 定义体力

cost(S)=∑i=1∣S∣∣HPi−HPi−1∣,P0=0,\mathrm{cost}(S) = \sum_{i=1}^{|S|} \bigl|H_{P_i} - H_{P_{i-1}}\bigr|, \qquad P_0 = 0,

即"从地面出发、按编号递增依次踩过 SS 中台阶"的总落差。求 cost(Sa)+cost(Sb)\mathrm{cost}(S_a) + \mathrm{cost}(S_b) 的最小值。

题面公式疑似漏写绝对值。 原文求和项写作 HPi−HPi−1H_{P_i} - H_{P_{i-1}},若照字面理解, 求和式会望远镜式相消成 HP∣S∣−H0=HP∣S∣H_{P_{|S|}} - H_0 = H_{P_{|S|}},于是总代价 =H链 a 的末台阶+H链 b 的末台阶= H_{\text{链 }a\text{ 的末台阶}} + H_{\text{链 }b\text{ 的末台阶}},把 NN 号台阶单独放一条链 (另一条全空)就能得到 HNH_N,样例 [1,3,1][1,3,1] 将输出 11 而不是 44。 补上绝对值后样例恰好是 44(Sa={1,3},Sb={2}S_a = \{1,3\}, S_b = \{2\}:1+3=41 + 3 = 4), 因此本题的真实模型是绝对差之和,下文一律按它推导。

正解

思路

朴素想法。 枚举每个台阶属于哪条链,2N2^N 种方案,逐方案算代价。 N⩽20N \leqslant 20 时勉强可行(对应 10% 档),NN 到 5×1055 \times 10^5 时完全不可行。

把"两条链"写成一条链 + 一个悬挂点。 关键是找一个能随下标推进的状态。 设 fi(x)f_i(x) = 处理完前 ii 个台阶、第 ii 个台阶是链 aa 的末尾、 链 bb 的末尾高度为 xx 时的最小总体力。任意一个划分方案,把两条链的末尾编号比较一下, 较大的那个必然是 NN,所以答案就是 min⁡xfN(x)\min_x f_N(x)。

递推只关心第 i+1i+1 个台阶接到哪条链上:

  1. 接在 ii 后面(仍在链 aa):链 aa 末尾变成 Hi+1H_{i+1},链 bb 末尾仍是 xx, 代价增加 ∣Hi+1−Hi∣|H_{i+1} - H_i|:
    fi+1(x)=fi(x)+c,c=∣Hi+1−Hi∣.f_{i+1}(x) = f_i(x) + c, \qquad c = |H_{i+1} - H_i|.
  2. 接到另一条链:链 bb 末尾变成 Hi+1H_{i+1},链 aa 末尾停在 HiH_i。 为了套回"链 aa 的末尾是第 i+1i+1 个台阶"这个形状,把两条链换个名字, 于是新状态的自变量是 HiH_i,取值是所有可能的旧 xx:
    fi+1(Hi)=min⁡x(fi(x)+∣Hi+1−x∣)=φi(Hi+1).f_{i+1}(H_i) = \min_x \bigl(f_i(x) + |H_{i+1} - x|\bigr) = \varphi_i(H_{i+1}).

第一式说明 x≠Hix \neq H_i 的那些位置只是整体加上同一个 cc;第二式只单点改写键 HiH_i。 于是只需维护一个"值域上的函数",每步一次全局加、一次单点下调,外加求 φ(h)=min⁡xf(x)+∣h−x∣\varphi(h) = \min_x f(x) + |h - x|。

锥形下包络拆成两半。 把 ∣h−x∣|h - x| 按 x⩽hx \leqslant h、x>hx > h 拆开:

φ(h)=min⁡(  h+min⁡x⩽h(f(x)−x),    −h+min⁡x>h(f(x)+x)  ).\varphi(h) = \min\Bigl(\; h + \min_{x \leqslant h}\bigl(f(x) - x\bigr),\;\; -h + \min_{x > h}\bigl(f(x) + x\bigr)\;\Bigr).

所以只要能在"值域上"查前缀最小值和后缀最小值,φ\varphi 就是 O(log⁡n)O(\log n) 的。 两个量 A(x)=f(x)−xA(x) = f(x) - x 与 B(x)=f(x)+xB(x) = f(x) + x 各自被单点下调, 而"全局加 cc"对它们的影响只是加 cc,用全局懒加 add 记账,数组里存 A−addA - \text{add}、B−addB - \text{add} 即可。

值域压缩。 xx 的候选只有地面 00 和某个 HjH_j(另一条链的末尾总归是某级台阶或地面), 把 00 与所有 HiH_i 排序去重后作为值域,R⩽N+1R \leqslant N + 1。

为什么单点下调写成 min 就够。 换链后键 Hi−1H_{i-1} 的真实新值是 min⁡(fi−1(Hi−1)+c,  t)\min\bigl(f_{i-1}(H_{i-1}) + c,\; t\bigr)。但 Hi−1H_{i-1} 本身是 xx 的合法取值, 所以 t=φi−1(Hi)⩽fi−1(Hi−1)+∣Hi−Hi−1∣=fi−1(Hi−1)+ct = \varphi_{i-1}(H_i) \leqslant f_{i-1}(H_{i-1}) + |H_i - H_{i-1}| = f_{i-1}(H_{i-1}) + c, 真实新值恒等于 tt,直接取 min⁡\min 不会漏。

答案的维护。 记 mi=min⁡xfi(x)m_i = \min_x f_i(x)。新状态要么来自 x≠Hix \neq H_i 的整体加 (候选 mi+cm_i + c),要么来自换链(候选 tt),故 mi+1=min⁡(mi+c, t)m_{i+1} = \min(m_i + c,\, t), 最后输出 mNm_N。

用样例 H=[1,3,1]H = [1,3,1] 走一遍(xx 只可能是 0,1,30, 1, 3):

步骤 动作 ff 的取值 mm
i=1i=1 初始化 f(0)=1f(0) = 1 11
i=2i=2 c=2c=2,t=φ(3)=1+3=4t=\varphi(3)=1+3=4 f(0)=3, f(1)=4f(0)=3,\ f(1)=4 min⁡(1+2, 4)=3\min(1+2,\ 4)=3
i=3i=3 c=2c=2,t=φ(1)=min⁡(3+1, 4+0)=4t=\varphi(1)=\min(3+1,\ 4+0)=4 f(0)=5, f(1)=4f(0)=5,\ f(1)=4 min⁡(3+2, 4)=4\min(3+2,\ 4)=4

输出 44,与样例一致。

代码

python
#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-07 21:59
# update_at: 2026-10-07 21:59

import sys
from bisect import bisect_left

INF = 1 << 62  # 无穷大哨兵:真实答案不超过 5e14,远小于它


def upd_min(tree: list[int], pos: int, val: int) -> None:
    """把 0 下标位置 pos 的值下调为 val(前缀最小树状数组只支持"变小")。"""
    i = pos + 1
    while i < len(tree):
        if val < tree[i]:
            tree[i] = val
        i += i & -i


def qry_min(tree: list[int], pos: int) -> int:
    """询问 0..pos 的最小值;pos < 0 表示区间为空,返回 INF。"""
    res = INF
    i = pos + 1
    while i > 0:
        if tree[i] < res:
            res = tree[i]
        i -= i & -i
    return res


def min_total(h: list[int]) -> int:
    """返回把台阶分给两条从地面出发的链后所需的最小总体力值。

    维护 f(x) = 前 i 个台阶里,第 i 个台阶是某条链末尾、另一条链末尾高度为 x 的最小体力。
    接在 i 后面只是全体加 |Δ|(懒加 add);换链则把另一条链接到 H_i 上,
    代价是锥形下包络 φ(h) = min( h + min_{x≤h}(f(x)-x), -h + min_{x>h}(f(x)+x) )。
    两棵树状数组分别维护 f(x)-x 与 f(x)+x,单点下调键 H_{i-1}。
    """
    xs = sorted({0, *h})                    # 候选的另一条链末尾高度:地面 0 加上所有台阶高度
    r = len(xs)
    tree_a = [INF] * (r + 1)                # f(x) - x 的前缀最小
    tree_b = [INF] * (r + 1)                # f(x) + x 的前缀最小(下标反转后查 x > h 的部分)

    add = 0                                 # 全局懒加:所有状态共同的增量
    ans = h[0]                              # f_1:第 1 个台阶自成一链,另一条停在地面
    k0 = bisect_left(xs, 0)
    upd_min(tree_a, k0, h[0])
    upd_min(tree_b, r - 1 - k0, h[0])

    for i in range(1, len(h)):
        c = abs(h[i] - h[i - 1])            # 接在同一条链后面的增量
        cur = h[i]
        pos = bisect_left(xs, cur)
        t = cur + qry_min(tree_a, pos) + add                    # x ≤ cur 一侧
        other = -cur + qry_min(tree_b, r - 2 - pos) + add       # x > cur 一侧
        if other < t:
            t = other
        ans = min(ans + c, t)               # 换链后键 H_{i-1} 的新值就是 t
        add += c
        k = bisect_left(xs, h[i - 1])
        base = t - add
        upd_min(tree_a, k, base - xs[k])
        upd_min(tree_b, r - 1 - k, base + xs[k])

    return ans


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n = next(data)
    h = [next(data) for _ in range(n)]
    print(min_total(h))


if __name__ == "__main__":
    solve()
cpp
/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-07 21:59
 * update_at: 2026-10-07 21:59
 */
// 一本通 1744《跳台阶》
// 把 N 个台阶分给两条链,每条链从地面(高度 0)出发,按台阶编号递增行走,
// 一条链的体力 = |首台阶高 - 0| + Σ|相邻两台阶高之差|(题面给出的求和式缺了绝对值,
// 由样例 [1,3,1] 答案为 4 可确认是绝对差之和,否则求和式会望远镜式相消变成 H_last)。
// 记 f_i(x) = 处理完前 i 个台阶、第 i 个台阶是某条链的末尾、另一条链末尾高度为 x 的最小总体力。
//   1) 第 i+1 个台阶接在 i 后面:f_{i+1}(x) = f_i(x) + |H_{i+1} - H_i|(整体懒加 c)
//   2) 第 i+1 个台阶换到另一条链:两条链末尾互换,f_{i+1}(H_i) = min_x f_i(x) + |H_{i+1} - x|
// 第二条即锥形下包络 φ(h) = min_x f_i(x) + |h - x|
//          = min( h + min_{x<=h}(f(x)-x),  -h + min_{x>h}(f(x)+x) ),
// 用两棵树状数组(前缀最小 / 反转下标后的前缀最小)维护 f(x)-x 与 f(x)+x 即可 O(log n) 求值,
// 单点下调键 H_i,全局懒加记录公共增量。答案 = min_x f_n(x),全程维护该最小值 m。
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int MAXN = 500005;      // 台阶数上限
const ll INF = 1LL << 62;     // 无穷大:真实答案不超过 5e14,远小于它

int n;                        // 台阶数
ll h[MAXN];                   // h[0..n-1] 即题面第 1..n 个台阶的高度
ll xs[MAXN];                  // 值域压缩后的候选"另一条链的末尾高度":地面 0 加上所有台阶高度
int R;                        // 压缩后点数
ll treeA[MAXN];               // 树状数组:前缀 min (f(x) - x)
ll treeB[MAXN];               // 树状数组:反转下标上的前缀 min,用来查 x > h 的 min (f(x) + x)
ll add;                       // 全局懒加:所有状态共同增加的量(树状数组里存的是减去 add 的值)

// 把 0 下标位置 pos 的值下调为 val(树状数组只能"变小",正好够用)
void upd_min(ll tree[], int pos, ll val) {
    for (int i = pos + 1; i <= R; i += i & -i) {
        if (val < tree[i]) tree[i] = val;
    }
}

// 询问 0..pos 的最小值;pos < 0 表示区间为空,返回 INF
ll qry_min(ll tree[], int pos) {
    ll res = INF;
    for (int i = pos + 1; i > 0; i -= i & -i) {
        if (tree[i] < res) res = tree[i];
    }
    return res;
}

// 值 x 在压缩值域中的下标
int rk(ll x) {
    return (int)(lower_bound(xs, xs + R, x) - xs);
}

int main() {
    if (scanf("%d", &n) != 1) return 0;
    for (int i = 0; i < n; i++) scanf("%lld", &h[i]);

    int tot = 0;
    xs[tot++] = 0;                                    // 空链的末尾就是地面
    for (int i = 0; i < n; i++) xs[tot++] = h[i];
    sort(xs, xs + tot);
    R = (int)(unique(xs, xs + tot) - xs);

    for (int i = 1; i <= R; i++) {                    // 树状数组 1 号下标起用
        treeA[i] = INF;
        treeB[i] = INF;
    }

    // 初始状态 f_1:第 1 个台阶自成一链,另一条链停在地面,体力 = H_1
    ll m = h[0];
    int p0 = rk(0);
    upd_min(treeA, p0, h[0]);
    upd_min(treeB, R - 1 - p0, h[0]);

    for (int i = 1; i < n; i++) {
        ll c = llabs(h[i] - h[i - 1]);                // 接在同一条链后面的增量
        ll cur = h[i];
        int pos = rk(cur);

        // 换链:φ(cur) = min( cur + min_{x<=cur}(f(x)-x),  -cur + min_{x>cur}(f(x)+x) )
        ll t = cur + qry_min(treeA, pos) + add;
        ll other = -cur + qry_min(treeB, R - 2 - pos) + add;   // x > cur 的部分(反转下标)
        if (other < t) t = other;

        m = min(m + c, t);                            // m 即 min_x f(x)
        add += c;
        // 键 H_{i-1} 的新值恰为 t(t <= f(H_{i-1}) + c 恒成立),单点下调即可
        int k = rk(h[i - 1]);
        ll base = t - add;
        upd_min(treeA, k, base - xs[k]);
        upd_min(treeB, R - 1 - k, base + xs[k]);
    }

    printf("%lld\n", m);
    return 0;
}

复杂度

时间 O(Nlog⁡N)O(N \log N)(排序 + 每个台阶常数次树状数组操作),空间 O(N)O(N)。 N=5×105N = 5 \times 10^5 时 C++ 实测最大点 0.087s,峰值内存 17.4MB。 Python 版是同一算法的同阶实现(树状数组换成 list + while 循环), 实测最大点 1.00s(其余 N=5×105N = 5 \times 10^5 的点 0.25 ~ 0.3s), 在 1s 限时边缘:若判 TLE,属于语言常数问题,算法本身没有降级。

总结

本题的建模难点是"两条链":把其中一条钉在"当前处理到的台阶"上,另一条的末尾高度当成函数 自变量,2N2^N 枚举就塌缩成一维 DP fi(x)f_i(x)。递推的两条分支恰好对应两种操作——全体加 (接在同一条链后面)与单点改写(换链,新值由锥形包络给出), 而 φ(h)=min⁡xf(x)+∣h−x∣\varphi(h) = \min_x f(x) + |h - x| 通过把绝对值按 x≲hx \lesssim h 拆成两半, 化为"前缀最小 / 后缀最小",用两棵树状数组 + 全局懒加维护,得到 O(Nlog⁡N)O(N \log N)。

几个容易踩的点:

  • 题面求和式漏了绝对值,必须按绝对差之和理解,否则样例对不上。
  • xx 的候选集只有 {0}∪{Hj}\{0\} \cup \{H_j\},压缩值域时别忘了把 00 放进去(空链对应 x=0x = 0)。
  • 换链时改写的键是上一个台阶的 Hi−1H_{i-1}(不是 HiH_i),因为换链后"链 aa 的末尾" 变成了原来第 i−1i-1 个台阶。
  • 单点更新只会让值变小,所以树状数组直接取 min⁡\min 即可,不需要支持"改大"。

素材说明: 本题素材目录里带 data.py 数据生成脚本,data/ 是自造的(分层覆盖 N=1N = 1、样例、N=2N = 2、随机、单调递增、全相等等情形),题面与官方原题可能有出入; 上述"公式漏绝对值"的判断也正来自样例反推。同目录 std.cpp 与本题解模型一致 (同为 O(Nlog⁡N)O(N \log N) 的包络 DP,差别只是它用两棵区间最值线段树、本题解用两棵前缀最小树状数组), 已用 data/ 全部 10 个点核对通过;另外用 n⩽11n \leqslant 11 的全枚举暴力对拍 300 组, C++ 与 Python 均无差异。