问题 25291 --架设电话线

25291: 架设电话线

时间限制: 1 Sec  内存限制: 128 MB
提交: 37  解决: 14
[提交][状态][讨论版][数据上传:][下载FPS1元][下载测试数据1元][612kb]

题目描述

最近,约翰的奶牛们越来越不满足于牛棚里一塌糊涂的电话服务,于是,她们要求约翰把那些老旧的电话线换成性能更好的新电话线。新的电话线架设在已有的n根电话线杆上,第i根电话线的高度为hi,(1=<hi<=100)。电话线总是从一根电话线杆的顶端被引到相邻的那根的顶端,如果这两根电话线杆的高度hi和hj不同,那么约翰就必须支付c*abs(hi-hj)的费用,当然,你不能移动电话线杆,只能按照原有的顺序在相邻杆间架设电话线。
加高某些电话线杆能减少架设电话线的总费用,尽管这项工作也需要支付一定的费用。更准确的说,如果他把一根电话线杆加高x米的话,他需要付出x^2费用。
请你帮约翰计算一下,如果合理的进行这两项工作,他最少要在这个电话线改造工程中花多少钱。

输入

第一行输入两个数n和c,含义如上
接下来n行,每行一个整数hi

输出

输出约翰完成电话线改造工程需要花费的最小费用

样例输入

5 2
2
3
5
1
4

样例输出

15

提示

【数据范围】

50%数据n<=1000,70%数据n<=10000,100%数据n<=100000,答案不超过maxlongint 

C<=100;

Hi<=100;

来源

[提交][状态]