/ OIer TK / 题库 /

旅行-2

旅行-2

测试数据来自 system/1661

背景

Orz5-2 swap

描述

今天又是个神圣的日子,因为LHX教主又要进行一段长途旅行。但是教主毕竟是教主,他喜欢走自己的路,让别人目瞪口呆。为什么呢,因为这条路线高低不平,而且是相当的严重。
但是教主有自己的办法,他会魔法。
这段路可以用一个长度为n的序列A[i]来表示,A[i]表示了第i这段路的高度。毕竟教主即使会使用魔法他还是个人,教主如果想穿越这条路线,他必须从第1段路开始走,走到第n段,从第i段走到第i+1段路需要消耗|A[i+1]-A[i]|点体力。为了节省体力,教主使出了他另一种神奇的魔法。教主的魔法可以交换相邻两段路的高度,并且这种魔法不需要花费额外的体力。但是第二次使用魔法开始,交换的两段路在路线中的位置需位于之前交换的两段路之后。即如果某次交换了A[j]和A[j+1],那么下次交换A[k]和A[k+1]必须满足j<k。

接着,LHX教主想规划下如何调整路段高度后穿越,使得体力消耗最小。

格式

输入格式

输入的第1行为一个正整数n,表示了这条路线的长度。
第2行有n个正整数,相邻两个正整数用空格隔开,描述了A[i]这个序列。

输出格式

输出仅包括一个非负整数,为最小的体力消耗。

样例1

样例输入1

4
2 3 4 1

样例输出1

4

限制

对于10%的数据,n≤10;
对于20%的数据,n≤18;
对于50%的数据,n≤200;
对于100%的数据,n≤2000,A[i]≤100000。

时限1s。

提示

将位置1上的数字和位置2上的数字交换,序列变为3 2 4 1。

将位置2上的数字和位置3上的数字交换,序列变为3 4 2 1。

序列3 4 2 1需要消耗的体力为4。

信息

ID
1609
难度
(无)
分类
动态规划 点击显示
标签
递交数
0
已通过
0
通过率
?
上传者