P4767 [IOI2000]邮局

四边形不等式，代码如下；

#include<bits/stdc++.h>
#define maxn 3010
#define n 310
#define inf 0x3f3f3f3f3f

using namespace std;

int v,p,x[maxn],
dp[maxn][n],//前i个村庄放j个邮局的最优方案 
w[maxn][maxn],//距离，预处理 
d[maxn][n];//前i个村庄放j个邮局放在哪里是最优策略 
int k;
void pre()
{
	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]+x[r]-x[(l+r)>>1];
		}
	}
	//w(i,j)表示村庄区间[i,j]内放一个村庄时该区间的最小距离总和。
}

int main()
{
	cin>>v>>p;
	for(int i=1;i<=v;i++) cin>>x[i];
	pre();
	sort(x+1,x+1+v);
	
	memset(dp,0x3f,sizeof(dp));
	dp[0][0]=0;
	
	for(int j=1;j<=p;j++){
		d[v+1][j]=v;
		for(int i=v;i>=1;i--){//因为需要用i+1更新i，所以倒序循环 
			int minn=inf,minnd;
			for(int k=d[i][j-1];k<=d[i+1][j];k++){
				if(dp[k][j-1]+w[k+1][i]<minn){
					minn=dp[k][j-1]+w[k+1][i];
					minnd=k;
				} 
			}
			
			dp[i][j]=minn;
			d[i][j]=minnd;
		}
	}
	
	cout<<dp[v][p]<<'
';
	return 0;
	
}