0x50 动态规划（0x51 线性DP）例题3：分级

P2893 [USACO08FEB] Making the Grade G

题目描述

有一条路总共 $N$ 段，每一段海拔是 $A_i$。

农夫约翰想改造这条路，修理后每一段的海拔是 $B_i$ ，花费 $|A_i - B_i|$。

要求修好之后这条路是单调不升（$B_i \ge B_j,i < j$）或者单调不降（$B_i \le B_j,i < j$）的。

求最小花费 $\sum(|A_i - B_i|)$。

输入格式

第一行一个整数 $N(1 \le N \le 2000)$ 。

下来 $N$ 个整数 $A_i(A_i \le 10^9)$ 。

输出格式

一行一个整数，表示最小花费。

输入输出样例 #1

输入 #1

7
1 3 2 4 5 3 9

输出 #1

3