Responsive image

问题 1584 --山区修路

1584: 山区修路

时间限制: 1 Sec  内存限制: 128 MB
提交: 7  解决: 4
[提交][状态][讨论版][命题人:]

题目描述

    某山区的孩子们上学必须经过一条凹凸不平的土路,每当下雨天,孩子们非常艰难。现在村里走出来的Dr. Kong决定募捐资金重新修建着条路。由于资金有限,为了降低成本,对修好后的路面高度只能做到单调上升或单调下降。
   为了便于修路,我们将整个土路分成了N段,每段路面的高度分别A1,A2,….,An。由于将每一段路垫高或挖低一个单位的花费成本相同,修路的总费用与路面的高低成正比。
现在Dr. Kong希望找到一个恰好含N个元素的不上升或不下降序列B1,B2,….,Bn,作为修过的路路段的高度。要求:
         | A1-B1| + | A2–B2| + ... + | An-Bn|------>最小

输入描述

第一行:    K                 表示有多少组测试数据。
接下来对每组测试数据:
第1行:       N                表示整个土路分成了N段
第2~N+1行: A1  A2 ……AN     表示每段路面的高度
2≤k≤10      0≤Ai≤10^7     0≤N≤500    (i=1,…, N)
所有数据都是整数。 数据之间有一个空格。
数据保证| A1-B1|+| A2-B2|+ ... +| An-Bn|的最小值不会超过10^9

输出描述

对于每组测试数据输出占一行| A1-B1|+| A2-B2|+ ... +| An-Bn|的最小值。 

样例输入

2
7
1 3 2 4 5 3 9
5
8 6 5 6 2

样例输出

3
1

提示

[DP]

来源

[提交][状态]
ACM算法攻关部