题解

思路

存在最优目标序列，其每个值都取自原序列的某个元素值：若某段目标值落在相邻两个原值之间，整体移动到端点不会增加绝对值距离。因此可离散化原值后动态规划。

更快的做法使用大根堆维护已经处理的目标值。读入 $x$ 时把它加入堆；若堆顶大于 $x$，说明当前最大目标值违反非递减性，把差值加入答案，并用 $x$ 替换这个堆顶。

做法

标程逐个处理 $a_i$：先把 $a_i$ 入堆；若堆顶大于 $a_i$，累加堆顶与 $a_i$ 的差并替换；最后再入堆一次。答案即累计差值。

独立 Oracle 对排序去重后的值 $v_j$ 计算 $dp[i][j]$：前 $i$ 项且第 $i$ 项目标不大于 $v_j$ 的最小代价，用前缀最小值滚动转移。短序列程序直接枚举非递减目标值下标。

正确性证明

堆中成对元素表示各前缀 L1 目标的中位数边界。若新值不小于堆顶，追加它不破坏非递减最优解；若更小，任何合法解必须把一个过大的边界降到不高于新值，至少付出堆顶减新值，替换恰好支付此下界且保持中位数不变量。归纳后累计值即全局最小代价。

复杂度

时间复杂度 $O(n\log n)$，空间复杂度 $O(n)$。