思路与算法

处理到高度prev时，一条路径最后访问了当前台阶，另一条路径最后高度记x。dp[x]表示最小费用。新高度h若接当前路径，所有状态统一加|h−prev|；若接另一条，得到新状态x=prev，候选min_x(dp[x]+|h−x|)。把统一增量单独记global，存dp−global；用前缀min(dp−global−x)、后缀min(dp−global+x)的两棵树状数组查询候选，压缩高度后点取小更新。

正确性说明

新台阶必分给两条路径之一，两种转移覆盖所有合法分组且保持原编号顺序。统一接当前路径只改变同一global；接另一条的最小式按x≤h和x≥h展开，正好是两类前后缀最小。候选存储值减去本轮统一增量后更新prev状态，维持dp−global不变量。点值只会变小，Fenwick最小更新有效，最终global加所有存储值最小即最优总费用。

复杂度

高度压缩排序O(N log N)，树状数组初始化O(N)，每台阶常数次O(log N)查询更新，总O(N log N)，空间O(N)。

易错点

原缺失绝对值已公开补正，不是可望远镜消去的有符号差。必须先用旧状态查询候选，再更新global。地面高度0参与压缩；空集合允许。dp−global可负，使用有符号64位。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll INF = 4000000000000000000LL;
struct BIT {
    int n;
    vector<ll> a;
    BIT(int n) : n(n), a(n + 1, INF) {
    }
    void put(int i, ll x) {
        for (; i <= n; i += i & -i)
            a[i] = min(a[i], x);
    }
    ll get(int i) {
        ll x = INF;
        for (; i; i -= i & -i)
            x = min(x, a[i]);
        return x;
    }
};
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    vector<ll> h(n), v{0};
    for (auto &x : h) {
        cin >> x;
        v.push_back(x);
    }
    sort(v.begin(), v.end());
    v.erase(unique(v.begin(), v.end()), v.end());
    int z = v.size();
    BIT lo(z), hi(z);
    lo.put(1, 0);
    hi.put(z, 0);
    ll global = 0, best = 0, prev = 0;
    for (ll x : h) {
        int rank = lower_bound(v.begin(), v.end(), x) - v.begin() + 1;
        ll q = min(lo.get(rank) + x, hi.get(z - rank + 1) - x);
        ll move = llabs(x - prev), nv = q - move;
        global += move;
        int old = lower_bound(v.begin(), v.end(), prev) - v.begin() + 1;
        lo.put(old, nv - prev);
        hi.put(z - old + 1, nv + prev);
        best = min(best, nv);
        prev = x;
    }
    cout << global + best << '\n';
}