因为两个人方案的对称性，可以将$k$除以$2$，转化为在$n-1$个间隔中设置若干断点，求第$k$小的增量。
对于选中的相邻的断点$(a,a+1)$和$(b,b+1)$，增量为$|x_a-x_{b+1}|$。
将绝对值拆开，用可持久化权值线段树优化建图，然后求$k$短路即可。
时间复杂度$O(nlog^2n+klog k)$。
#include<cstdio>
#include<algorithm>
#include<queue>
#include<vector>
using namespace std;
typedef long long ll;
typedef pair<ll,int>P;
const int MAXN=10010,N=400000,M=2000000;
const ll inf=1LL<<60;
int n,K,i,a[MAXN],b[MAXN],T0,T1,l[N],r[N],tot;ll base,ans;
namespace G{
int n,m,i,S,T,g[N],v[M],u[M],w[M],nxt[M],f[N],h[N],tot;ll d[N];bool is[M],vis[N];
struct Node{
int l,r,d;P v;
Node(){}
Node(int _l,int _r,int _d,P _v){l=_l,r=_r,d=_d,v=_v;}
}pool[M*4];
inline int build(P v){
pool[++tot]=Node(0,0,0,v);
return tot;
}
int merge(int a,int b){
if(!a||!b)return a+b;
if(pool[a].v>pool[b].v)swap(a,b);
int x=++tot;
pool[x]=pool[a];
pool[x].r=merge(pool[a].r,b);
if(pool[pool[x].l].d<pool[pool[x].r].d)swap(pool[x].l,pool[x].r);
pool[x].d=pool[x].r?pool[pool[x].r].d+1:0;
return x;
}
void cal(int x){
if(vis[x])return;
vis[x]=1;
d[x]=inf,f[x]=0;
if(x==T){d[x]=0;return;}
for(int i=g[x];i;i=nxt[i]){
cal(u[i]);
if(d[u[i]]+w[i]<d[x])d[x]=d[u[i]]+w[i],f[x]=i;
}
}
void dfs(int x){
if(!f[x]||vis[x])return;
vis[x]=1;
dfs(u[f[x]]);
h[x]=merge(h[x],h[u[f[x]]]);
}
inline void add(int x,int y,int z){
if(!x||!y)return;
v[++m]=x;u[m]=y;w[m]=z;nxt[m]=g[x];g[x]=m;
}
void solve(){
for(i=1;i<=n;i++)cal(i);
ans=d[S];
if(K==1)return;
K--;
for(i=1;i<=n;i++)vis[i]=0,is[f[i]]=1;
for(i=1;i<=m;i++)if(!is[i]&&d[u[i]]<inf)h[v[i]]=merge(h[v[i]],build(P(w[i]-d[v[i]]+d[u[i]],u[i])));
for(i=1;i<=n;i++)dfs(i);
priority_queue<P,vector<P>,greater<P> >q;
ll x,y;
y=h[S];
if(y)q.push(P(d[S]+pool[y].v.first,y));
while(!q.empty()&&K){
K--;
P t=q.top();q.pop();
ans=t.first;
x=t.second,y=pool[x].l;
if(y)q.push(P(ans-pool[x].v.first+pool[y].v.first,y));
y=pool[x].r;
if(y)q.push(P(ans-pool[x].v.first+pool[y].v.first,y));
y=h[pool[x].v.second];
if(y)q.push(P(ans+pool[y].v.first,y));
}
}
}
int ins(int x,int a,int b,int c,int X,int W){
int y=++tot;
if(a==b){
G::add(X,y,W);
return y;
}
int mid=(a+b)>>1;
if(c<=mid)l[y]=ins(l[x],a,mid,c,X,W),r[y]=r[x];
else l[y]=l[x],r[y]=ins(r[x],mid+1,b,c,X,W);
G::add(l[y],y,0),G::add(r[y],y,0);
return y;
}
void ask(int x,int a,int b,int c,int d,int X,int W){
if(!x)return;
if(c<=a&&b<=d){
G::add(x,X,W);
return;
}
int mid=(a+b)>>1;
if(c<=mid)ask(l[x],a,mid,c,d,X,W);
if(d>mid)ask(r[x],mid+1,b,c,d,X,W);
}
int main(){
scanf("%d%d",&n,&K);
K=(K+1)/2;
for(i=1;i<=n;i++){
scanf("%d",&a[i]);
b[i]=a[i];
base+=abs(a[i]-a[i-1]);
}
sort(b,b+n+1);
for(i=0;i<=n;i++)a[i]=lower_bound(b,b+n+1,a[i])-b;
G::S=1;
G::T=2;
tot=2;
G::add(1,2,0);
for(i=1;i<n;i++){
int x=++tot,w=-abs(b[a[i]]-b[a[i+1]]);
G::add(1,x,w+abs(b[a[i+1]]));
G::add(x,2,0);
ask(T0,0,n,0,a[i+1],x,w+b[a[i+1]]);
if(a[i+1]<n)ask(T1,0,n,a[i+1]+1,n,x,w-b[a[i+1]]);
T0=ins(T0,0,n,a[i],x,-b[a[i]]);
T1=ins(T1,0,n,a[i],x,b[a[i]]);
}
G::n=tot;
G::solve();
return printf("%lld",ans+base),0;
}