题解

思路

令 $f_i(x)$ 表示固定 $A_i=x$ 后，从第 $i$ 项到末尾能取得的最小代价。

做法

可以归纳证明，在区间 $[L_i,R_i]$ 中使 $f_i$ 最小的所有整数总构成一个区间 $[l_i,r_i]$。末项有 $[l_N,r_N]=[L_N,R_N]$；向前转移时，若当前区间在 $[l_{i+1},r_{i+1}]$ 左侧，则只有 $R_i$ 最优，若在其右侧则只有 $L_i$ 最优，否则最优区间就是两者交集。由此可从后向前在线性时间求出全部 $l_i,r_i$。

为了取得字典序最小的最优序列，先取 $A_1=l_1$。已经确定 $A_{i-1}$ 后，最小化 $|A_i-A_{i-1}|+f_i(A_i)$ 的最小可选整数为 $A_i=\max(L_i,\min(A_{i-1},r_i))$；该选择既保持后缀最优，又在当前位置尽可能小。

复杂度

两次线性扫描即可完成，时间复杂度为 $O(N)$，空间复杂度为 $O(N)$。