http://www.tsinsen.com/

清橙网格自动评测系统

>> 用户名或邮箱:   密码:       忘记密码   其他登录:
 
 
 
A1315. 积木(沈添笑)
时间限制:1.5s   内存限制:256.0MB  
总提交次数:   AC次数:   平均分:
将本题分享到:
   
 
问题描述
  搭积木是xx最喜欢的游戏之一。xx有n块高低不同的积木,她将它们排成一列。xx希望积木看起来尽可能的整齐,她将相邻两块积木高度之差的绝对值之和乘上系数c定义为积木序列的混乱值,显然,混乱值越小越好。xx可以通过调整积木的高度使其混乱值变小,她可以花费t^2的代价,往某块积木上再搭一块高为t(t为任意自然数)的积木,在同一块积木上只能搭一次。
  xx想考考你,混乱值与花费之和的最小值是多少呢?
输入格式
  输入的第一行包含两个整数n, c。接下来n行,第i行一个整数hi,代表第i块积木的高度。
输出格式
  输出一个整数,代表最小花费。
样例输入
4 1
1
2
1
3
样例输出
3
数据规模和约定
  20%的数据满足:n、h≤100
  40%的数据满足:n、h≤1000
  60%的数据满足:n≤1000
  80%的数据满足:n≤100000
  100%的数据满足:1≤n、h、c≤1000000