首先根据贪心,选相邻的减肯定比选间隔的减要更优,那么就有DP式:

$f_i=\min\limits_{k\le j\le i-k}\{f_j+s_i-s_j-a_{j+1}*(i-j)\}$

转化成关于$f_j-s_j+a_{j+1}*j=i*a_{j+1}+f_i-s_i$的一条直线就好了,之后维护下凸壳求截距最小就好了。

比较斜率的时候用这个柿子。

$f_k-s_k+a_{k+1}*k-f_j+s_j-a_{j+1}*j<i*(a_{k+1}-a_{j+1})$

单独处理一下$[k,2*k-1]$。

#include<cstdio>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#define gc getchar()
#define ll long long
using namespace std;
const int N=5e5+10;
template<class o>
inline void qr(o &x)
{
    x=0;char c=gc;
    while(c<'0'||c>'9')c=gc;
    while(c>='0'&&c<='9'){x=x*10+(c^48);c=gc;}
}
void qw(ll x)
{
    if(x<0)x=-x,putchar('-');
    if(x/10)qw(x/10);
    putchar(x%10+48);
}
ll a[N],s[N],f[N];int q[N];
inline bool slop(int i,int j,int k)
{
    ll wi=f[i]-s[i]+a[i+1]*i,wj=f[j]-s[j]+a[j+1]*j,wk=f[k]-s[k]+a[k+1]*k;
    return (wj-wi)*(a[k+1]-a[j+1])>=(wk-wj)*(a[j+1]-a[i+1]);
}
int main()
{
    int T;qr(T);
    while(T--)
    {
        int n,k;qr(n);qr(k);
        for(int i=1;i<=n;i++)qr(a[i]),s[i]=s[i-1]+a[i];
        for(int i=k;i<=2*k-1;i++)f[i]=s[i]-a[1]*i;
        int l=1,r=1;q[1]=k;
        for(int i=2*k;i<=n;i++)
        {
            while(l<r&&(f[q[l+1]]-s[q[l+1]]+a[q[l+1]+1]*q[l+1])-(f[q[l]]-s[q[l]]+a[q[l]+1]*q[l])<=i*(a[q[l+1]+1]-a[q[l]+1]))++l;
            f[i]=f[q[l]]+s[i]-s[q[l]]-a[q[l]+1]*(i-q[l]);
            while(l<r&&slop(q[r-1],q[r],i-k+1))--r;
            q[++r]=i-k+1;
        }
        qw(f[n]);puts("");
    }
    return 0;
}