最小花费

问题描述

农夫约翰想改造一条路，原来的路的每一段海拔是 $A_i$，修理后是 $B_i$，花费为 $|A_i - B_i|$。我们要求修好的路是单调不降的（即 $B_1 \le B_2 \le \dots \le B_N$）。求改造这条道路的最小总花费。

输入格式

第一行一个整数 $N$（$1 \le N \le 2000$）。 第二行 $N$ 个整数，表示数组 $A[1..N]$（$1 \le A[i] \le 2000$）。

输出格式

输出一个整数，表示满足条件的最小总花费。

样例输入

7
1 3 2 4 5 3 9

样例输出

3

样例解释

对于输入序列 $A = [1, 3, 2, 4, 5, 3, 9]$，可以构造一个单调不降的序列 $B$，使得总花费 $\sum |A_i - B_i|$ 最小。 例如最优方案为 $B = [1, 2, 2, 4, 5, 5, 9]$，总花费为 $|1-1| + |3-2| + |2-2| + |4-4| + |5-5| + |3-5| + |9-9| = 0+1+0+0+0+2+0 = 3$，与样例输出一致。

数据范围与约定

• $1 \le N \le 2000$
• $1 \le A[i] \le 2000$