3697: 旅行-【2014暑期训练】T7Day1T1

1. 旅行

【问题描述】

一段路可以用一个长度为N的序列A[I]来表示，A[I]表示了第I这段路的高度。第1段路开始走，走到第N段，从第I段走到第I+1段路需要消耗|A[I+1]-A[I]|点体力。

现在可以将一段路高度变高或者变低，改变一段路H的高度就需要消耗H的体力。即若把第I段路高度从A[I]变成了K，那么需要消耗|A[I]-K|点体力。

如何调整路段高度，使得总体力消耗最小。

【文件输入】

第1行为一个正整数N，表示了这条路线的长度。

第2行有N个正整数，相邻两个正整数用空格隔开，描述了A[I]这个序列。

【文件输出】

一个非负整数，为最小的总体力消耗。

【输入样例1】

3

3 4 1

【输出样例1】

3

【输入样例2】

10

1 2 3 4 3 2 1 2 3 4

【输出样例3】

7

【样例1说明】

将第2段路的高度调整为3，第3段路的高度调整为2，调整体力消耗为2。

路线序列变为3 3 2，穿越这条路线消耗体力为1。

所以总体力消耗为3。

【数据规模】

对于10%的数据，有N≤10；

对于30%的数据，有A[I]≤1000；

对于40%的数据，有N≤1000；

对于100%的数据，有N≤100000，A[I]≤10000000。