蒟蒻不懂四边形不等式优化，只会打暴力

#include <bits/stdc++.h>
#define int long long 
using namespace std;
const int N=3005;
int a[N],dp[N][N],w[N][N];
int v,p;
//int w_2(int l,int r)
//{
//	int mid=(l+r)>>1,ans=0;//建在mid上 
//	for (int i=l;i<mid;++i)
//	{
//		ans+=a[mid]-a[i];
//	}
//	for (int i=mid+1;i<=r;++i)
//	{
//		ans+=a[i]-a[mid];
//	}
//	return ans;
//}
void init()
{
	for (int i=1;i<=v;++i)
	{
		for (int j=i;j<=v;++j)
		{
			int mid=(i+j)>>1;
			w[i][j]=w[i][j-1]+a[j]-a[mid];
		}
	}
}
signed main() 
{
	cin >> v >> p;
	for (int i=1;i<=v;++i)
	{
		cin >> a[i]; 
	}
	init();
	memset(dp,0x3f,sizeof(dp));
	dp[0][0]=0;
	sort(a+1,a+v+1);
	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[i][j],dp[k][j-1]+w_2(k+1,i));
				dp[i][j]=min(dp[i][j],dp[k][j-1]+w[k+1][i]);
			}
		}
	}
	cout << dp[v][p] << '\n';
	return 0;
}

70 pts,TLE on #5 #6 #7