把台阶分给两条从地面出发的链,代价是各链绝对差之和;用「一条链停在 H_i、另一条停在 x」的 DP 加锥形下包络,两棵树状数组维护前缀最小做到 O(n log n)。
OJ: roj
题目 ID: 1744
难度:提高+/省选-
标签:动态规划树状数组数据结构python
创建: 2026-10-07 21:59
更新: 2026-10-07 21:59
形式化题目
有
即"从地面出发、按编号递增依次踩过
题面公式疑似漏写绝对值。 原文求和项写作
正解
思路
朴素想法。 枚举每个台阶属于哪条链,
把"两条链"写成一条链 + 一个悬挂点。 关键是找一个能随下标推进的状态。
设
递推只关心第
- 接在
后面(仍在链 ):链 末尾变成 ,链 末尾仍是 , 代价增加 : - 接到另一条链:链
末尾变成 ,链 末尾停在 。 为了套回"链 的末尾是第 个台阶"这个形状,把两条链换个名字, 于是新状态的自变量是 ,取值是所有可能的旧 :
第一式说明
锥形下包络拆成两半。 把
所以只要能在"值域上"查前缀最小值和后缀最小值,add 记账,数组里存
值域压缩。
为什么单点下调写成 min 就够。 换链后键
答案的维护。 记
用样例
| 步骤 | 动作 | ||
|---|---|---|---|
| 初始化 | |||
输出
代码
#!/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()/**
* 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;
}复杂度
时间 list + while 循环),
实测最大点 1.00s(其余
总结
本题的建模难点是"两条链":把其中一条钉在"当前处理到的台阶"上,另一条的末尾高度当成函数
自变量,
几个容易踩的点:
- 题面求和式漏了绝对值,必须按绝对差之和理解,否则样例对不上。
的候选集只有 ,压缩值域时别忘了把 放进去(空链对应 )。 - 换链时改写的键是上一个台阶的
(不是 ),因为换链后"链 的末尾" 变成了原来第 个台阶。 - 单点更新只会让值变小,所以树状数组直接取
即可,不需要支持"改大"。
素材说明: 本题素材目录里带
data.py数据生成脚本,data/是自造的(分层覆盖、样例、 、随机、单调递增、全相等等情形),题面与官方原题可能有出入; 上述"公式漏绝对值"的判断也正来自样例反推。同目录 std.cpp与本题解模型一致 (同为的包络 DP,差别只是它用两棵区间最值线段树、本题解用两棵前缀最小树状数组), 已用 data/全部 10 个点核对通过;另外用的全枚举暴力对拍 300 组, C++ 与 Python 均无差异。