2969. [USACO Feb08] 路面修整

【题目描述】

FJ 打算好好修一下农场中某条凹凸不平的土路。按奶牛们的要求，修好后的路面高度应当单调上升。整条路被分成了 $N(1\le N\le 2,000)$ 段，$N$ 个整数 $A_1,A_2,\dots ,A_N(0\le A_i\le 1,000,000,000)$ 依次描述了每一段路的高度。FJ 希望找到一个恰好含 $N$ 个元素的不下降序列 $B_1,\dots , B_N$，作为修过的路中每个路段的高度。由于将每一段路垫高或挖低一个单位的花费相同，修路的总支出可以表示为： $\vert A_1-B_1\vert +\vert A_2 -B_2\vert +\dots +\vert A_N-B_N\vert$ 请你计算一下，FJ 在这项工程上的最小支出是多少。FJ 向你保证，这个支出不会超过 $2^{31}-1$。

【输入格式】

第 $1$ 行：输入 $1$个整数 $N$。

第 $2\dots N+1$ 行：第 $i+1$ 行为 $1$ 个整数 $A_i$。

【输出格式】

第 $1$ 行：输出 $1$ 个正整数，表示FJ把路修成高度不下降的最小花费。

【样例输入】

7
1
3
2
4
5
3
9

【样例输出】

3

【样例说明】

FJ 将第一个高度为 $3$ 的路段的高度减少为 $2$，将第二个高度为 $3$ 的路段的高度增加到 $5$，总花费为 $\vert 2-3\vert +\vert 5-3\vert =3$，并且各路段的高度为一个不下降序列 $1,2,2,4,5,5,9$。

【来源】

USACO 2008 February Gold Division