Responsive image

问题 B: 抠门的乐园管理者

问题 B: 抠门的乐园管理者

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

题目描述

         迪士泥乐园准备在山区之间修建一个过山车的娱乐项目，经过勘测分析，途中需要经过高度分别为H1，H2，……,Hn的N个山区。由于高低不平，除正常的修建开支外，每段还要多出高度差|Hi - Hi-1|*X万元的斜坡费用。而迪士泥乐园修建这个过山车项目的管理员秦墨是个抠门的人，决定通过填高一些区域的高度来降低总的费用。当然填高也是需要一些费用的。每填高Y单位，需要付出Y2万元费用。

你能否帮秦墨做出一个规划，通过部分填高工程改造，使得总的费用降下来。

输入描述

第一行： T        表示以下有T组测试数据             （ 1≤ T ≤8 ）

对每组测试数据，  

第一行：N  X                     （2 ≤ N ≤100，000   1≤ X ≤100）

第二行：N个整数，分别表示N个区域的高度Hi       ( 1<=Hi<=100 , i=1…. n)

输出描述

对每组测试数据，输出占一行，一个整数，即经过部分填高工程改造后的最少费用。

样例输入

1
5 2
2 3 5 1 4

样例输出

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