话说这题很久以前就写过，然后好像一直忘了写题解……
以前看这道题还觉得挺难的，现在觉得好水
首先朴素的想法肯定是动归
f[i,j]表示到处理到第i根电线，最终高度为j的最小花费
f[i,j]:=min(f[i-1,k]+sqr(h[i]-j)+abs(j-k)*c) （h[i]<=j<=max) max为原来所有电线最高的高度
但这个会超时，我们就要想办法优化；
考虑这样一个方程式f[i,j]:=min(f[i-1,k]+sqr(h[i]-j)+(j-k)*c);
我们很容易用O(max)的时间完成转移（好像之前有过例子）；
但这个方程式多了一个绝对值，根据数学上的思想，我们就去绝对值讨论呗；
容易整理得到
f[i,j]=min(min(f[i-1,k]-k*c+j*c) j>=k, min(f[i-1,k]+k*c-j*c) j<=k)+sqr(h[i]-j)
这样不难想到，令
tal[j]=min(f[i-1,k]+k*c) k∈[j,max];
sho[j]=min(f[i-1,k]-k*c) k∈[h[i-1],j]
tal[j]表示上一根电线杆状态高度大于当前电线杆高度j高的花费中的最小值
sho[j]表示上一根电线杆状态高度小于当前电线杆高度j高的花费中的最小值
然后弄弄就出来了
const hmax=;
inf=;
var h:array[..] of longint;
sho,tal:array[..] of longint;
f:array[..,..] of longint;
i,k1,k2,n,m,j,c,ans:longint;
function min(a,b:longint):longint;
begin
if a>b then exit(b) else exit(a);
end; begin
readln(n,c);
for i:= to n do
begin
readln(h[i]);
if h[i]>m then m:=h[i];
end;
h[n+]:=h[i];
k1:=;
k2:=;
for i:=h[] to m do
f[,i]:=sqr(i-h[]);
for i:= to n do
begin
k1:=k1 xor ;
k2:=k2 xor ;
for j:= to m do
begin
tal[j]:=inf;
sho[j]:=inf;
f[k2,j]:=inf;
end;
tal[m]:=f[k1,m]+c*m;
for j:=m- downto h[i-] do
tal[j]:=min(tal[j+],f[k1,j]+c*j);
sho[h[i-]]:=f[k1,h[i-]]-c*h[i-];
for j:=h[i-]+ to m do
sho[j]:=min(sho[j-],f[k1,j]-c*j);
for j:=h[i] to m do
if j<h[i-] then
f[k2,j]:=min(f[k2,j],tal[h[i-]]-c*j+sqr(j-h[i])) //注意细节，这时候上一根电线杆不存在比这根矮的状态
else
f[k2,j]:=min(f[k2,j],min(tal[j]-c*j,sho[j]+c*j)+sqr(j-h[i]));
end;
ans:=inf;
for i:=h[n] to m do
ans:=min(ans,f[k2,i]);
writeln(ans);
end.