Rt,O(PVlog)的算法,结果比答案优是啥操作
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define pre(i,a,b) for(int i=a;i>=b;i--)
#define N 3005
#define M 305
using namespace std;
int n,m,a[N],f[N][M],s[N];
int calc(int x,int y){
int l=x,r=y,ans;
while(l<=r){
int mid=(l+r)>>1;
if(a[mid]-a[x]<=a[y]-a[mid])ans=mid,l=mid+1;
else r=mid-1;
}
return s[ans]-s[x-1]-a[x]*(ans-x+1)+a[y]*(y-ans)-(s[y]-s[ans]);
}
void solve(int l,int r,int ll,int rr,int op){
if(l>r)return;
int mid=(l+r)>>1;
if(ll>=mid)return;
int mn=ll;
rep(i,ll,min(mid-1,rr))if(f[i][op-1]+calc(i,mid)<=f[mn][op-1]+calc(mn,mid))mn=i;
f[mid][op]=f[mn][op-1]+calc(mn,mid);
solve(l,mid-1,ll,mn,op);solve(mid+1,r,mn,rr,op);
}
int main(){
//freopen("input","r",stdin);
scanf("%d%d",&n,&m);
rep(i,1,n)scanf("%d",&a[i]),s[i]=s[i-1]+a[i];
sort(a+1,a+n+1);
memset(f,0x3f,sizeof(f));
rep(i,1,n)f[i][1]=a[i]*i-s[i];//,cout<<f[i][1]<<" ";cout<<endl;
//rep(i,1,n)rep(j,i+1,n)printf("%d %d %d\n",i,j,calc(i,j));
rep(j,2,m){
solve(j,n,j-1,n-1,j);
//cout<<endl;
}
int ans=0x3f3f3f3f;
rep(i,m,n)ans=min(ans,f[i][m]+a[n]*(n-i+1)-(s[n]-s[i-1]));//,cout<<i<<" "<<f[i][m]<<endl;//cout<<endl;
printf("%d\n",ans);
return 0;
}