f[i,j].i表示第i个点,j=1表示上升0表示下降。
k是把环形分成长度为n的k段
谢谢了
var n,m,i,j,k,t:longint;
a:array[0..20009]of longint;
f:array[0..20009,0..1]of longint;
ans:array[1..10000]of longint;
function min(x,y:longint):longint;
begin
if x<y then min:=x
else min:=y;
end;
begin
readln(n,m);
for i:=1 to n do begin
read(j);
a[i]:=j;
a[i+n]:=j;
end;
for k:=1 to n-1 do begin
f[k,1]:=0; f[k,0]:=0;
for i:=k+1 to k+n do
for j:=0 to 1 do begin
if j=1 then if (a[i-1]-a[i])<0 then
f[i,j]:=min(f[i-1,0]+m,f[i-1,1])+abs(a[i-1]-a[i])
else
f[i,j]:=min(f[i-1,0]+m,f[i-1,1])+abs(a[i-1]-a[i])*abs(a[i-1]-a[i]);
if j=0 then if a[i-1]-a[i]>0 then
f[i,j]:=min(f[i-1,0],f[i-1,1]+m)+abs(a[i-1]-a[i])
else
f[i,j]:=min(f[i-1,0],f[i-1,1]+m)+abs(a[i-1]-a[i])*abs(a[i-1]-a[i]);
end;
ans[k]:=min(f[k+n,1],f[k+n,0]);
end;
m:=maxlongint;
for i:=1 to n-1 do
if ans[i]<m then m:=ans[i];
writeln(m);
end.