题目描述

FJ的农场里有一条笔直的土路连接两块田地，但这条路的海拔变化超出了他的期望。他的奶牛不介意爬上或爬下一个斜坡，但不喜欢连续交替的山丘和山谷。FJ希望通过添加或移除泥土，使这条路变成一个单调的斜坡（要么一直向上倾斜，要么一直向下倾斜）。

给定 $N$ 个整数 $A_1, \ldots, A_N$（$1 \leq N \leq 2000$），表示从第一块田地到另一块田地之间 $N$ 个等距位置的海拔高度（$0 \leq A_i \leq 10^9$）。FJ希望将这些海拔高度调整为一个新的序列 $B_1, \ldots, B_N$，使其要么非递增，要么非递减。由于在道路上任何位置添加或移除泥土的成本相同，修改道路的总成本为：

请计算将道路修整为连续斜坡的最小成本。FJ很高兴地告诉你，计算答案肯定可以使用有符号32位整数。

输入格式

• 第1行：一个整数 $N$
• 第2到 $N+1$ 行：第 $i+1$ 行包含一个整数 $A_i$，表示第 $i$ 个位置的海拔高度

输出格式

• 第1行：一个整数，表示FJ将土路修整为非递增或非递减海拔的最小成本

输入数据示例1

7
1
3
2
4
5
3
9

输出数据示例1

3

数据说明

• 样例解释：将海拔调整为非递减序列 $[1, 3, 3, 4, 5, 5, 9]$，总成本为 $|2-3| + |3-5| = 3$。

解题思路

1. 问题转化：寻找一个非递增或非递减序列 $B$，使 $\sum_{i=1}^{N} |A_i - B_i|$ 最小。
2. 算法选择：使用动态规划结合离散化优化，时间复杂度 $O(N^2 \log N)$。
3. 关键点：
   • 离散化：将所有可能的 $B_i$ 离散化为原始 $A_i$ 的值或相邻 $A_i$ 的平均值。
   • 状态转移：维护前 $i$ 个位置的最小成本，枚举当前位置的可能值，确保序列单调性。

提示：对于非递增情况，可将序列反转后转为非递减问题求解。