/*********************************
Note:
*********************************/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<fstream>
#include<cmath>
#include<cstring>
#include<string>
#include<queue>
using namespace std;
const int N = 3105;
int sum[N];
int a[N];
int f[3100][310]; // 前i个村庄里，安装j个邮局
int num[3100][310];
int calc(int l , int r)
{
	int mid= (l+r) >> 1;
	return  a[mid]*(mid-l+1) - sum[mid] + sum[l-1]  +  // 左边
			sum[r] - sum[mid] - a[mid]*(r-mid);   // 右边
} 

int main()
{
	int n , p;
	cin >> n >> p;
	for(int i = 1 ; i <= n ; i++)
	{
		cin >> a[i];
		sum[i] += sum[i-1] + a[i];
	}
	memset( f , 0x3f , sizeof(f) );
	f[0][0] = 0;
	for(int j = 1 ;j <= p ; j++)
	{
		num[n+1][j] = n;
		for(int i = n; i >= 1 ;i--)
		{
			for(int k = num[i][j-1] ; k <= num[i+1][j] ; k++)
			{
				int t = calc( k+1, i );
				if(f[i][j] > t + f[k][j-1])
				{
					num[i][j] = k;
					f[i][j] = t + f[k][j-1];
				}
			}
		}
	}
	cout << f[n][p] << endl;
    return 0;
}

WSSB

#include<iostream> 
#include<algorithm>       
#include<cstring>
using namespace std; 
int V, P, dp[3005][305], a[3005], w[3005][3005];

int main(){
	cin >> V >> P;
    for(int i = 1; i <= V; i++)
        cin >> a[i];
    sort(a+1, a+V+1);

    for(int l=1; l <= V; l++) {
		w[l][l] = 0;
		for(int r = l+1; r <= V; r++) {
			w[l][r] = w[l][r-1] + a[r] - a [(l+r)/2];
		}
	}

    memset(dp, 0x3f, sizeof(dp));
    dp[0][0] = 0;

    for(int i = 1; i <= V; i++)
        for(int j = 1; j <= P; j++)
            for(int k = 0; k < i; k++) 
				dp[i][j] = min(dp[k][j-1] + w[k+1][i], dp[i][j]);
    cout << dp[V][P] << endl;
    return 0;
}

#include <bits/stdc++.h> #define int long long using namespace std; int n,p,a[305],f[305][35],d[305][305]; main() { cin>>n>>p; for(int i=1;i<=n;i++) cin>>a[i]; sort(a+1,a+1+n); memset(f,127,sizeof f); for(int i=1;i<=n;i++) for(int j=i+1;j<=n;j++) d[i][j]=d[i][j-1]+a[j]-a[(i+j)/2]; for(int i=1;i<=n;i++) f[i][1]=d[1][i]; for(int i=2;i<=n;i++) for(int j=1;j<=p;j++) for(int k=j-1;k<i;k++) f[i][j]=min(f[i][j],f[k][j-1]+d[k+1][i]); cout<<f[n][p]; return 0; }