poj3709

首先我们发现将一段数变为同一个数比间隔着搞肯定优，
因为数列是升序的，
然后不难得到方程式f[i]=min(f[j]+sum[i]-sum[j]-(i-j)*a[j+1]) (i-j>=m)
简单的斜率优化不多说
注意这道题最优解有选择范围，也就是说要延迟入队

 var a,s,f:array[..] of int64;

     q:array[..] of longint;

     j,t,i,n,m,h,r:longint;

 function G(j,k:int64):int64;

   begin

     exit(f[j]-f[k]+s[k]-s[j]+a[j+]*j-a[k+]*k);

   end;

 function P(j,k:int64):int64;

   begin

     exit(a[j+]-a[k+]);

   end;

 function value(i,j:int64):int64;

   begin

     exit(f[j]+s[i]-s[j]-a[j+]*(i-j));

   end;

 begin

   readln(t);

   while t> do

   begin

     dec(t);

     readln(n,m);

     s[]:=;

     for i:= to n do

     begin

       read(a[i]);

       s[i]:=s[i-]+a[i];

     end;

     f[]:=;

     q[]:=;

     h:=;

     r:=;

     for i:= to n do

     begin

       while (h<r) and (G(q[h+],q[h])<=int64(i)*P(q[h+],q[h])) do inc(h);

       f[i]:=value(i,q[h]);

       if (i>=*m-) and (i<>n) then

       begin

         while (h<r) and (G(i-m+,q[r])*P(q[r],q[r-])<=G(q[r],q[r-])*P(i-m+,q[r])) do dec(r);

         inc(r);

         q[r]:=i-m+;

       end;

     end;

     writeln(f[n]);

   end;

 end.