https://www.luogu.org/problemnew/show/P4767
四边形不等式好题!
可以设f[i][j]表示前i个村庄，建了j个邮局的最小代价。
转移：f[i][j]=min{f[k][j-1]+dis[k+1][i]}
也就是枚举断点，断点后整个区间建造一个邮局并强制整个区间都选择它。
这个邮局在哪里最优呢？由人类智慧知，在中位数处最优。
注意到这样的转移下，时间复杂度是O(m*n^2)的，不行
这是一个前缀问题，但是同时它也是一个区间问题，回忆四边形不等式的形式，尝试套上去
至此，我们就有了O(nm)的优秀做法。
（证明暂时不会，有会证明的欢迎留言..）
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio> using namespace std; inline int rd(){
int ret=,f=;char c;
while(c=getchar(),!isdigit(c))f=c=='-'?-:;
while(isdigit(c))ret=ret*+c-'',c=getchar();
return ret*f;
} const int MAXN=; int n,m;
int val[MAXN],sum[MAXN],dis[MAXN][MAXN];
int f[MAXN][],tran[MAXN][]; int main(){
memset(f,0x3f,sizeof(f));
n=rd();m=rd();
for(int i=;i<=n;i++) val[i]=rd();
sort(val+,val++n);
for(int i=;i<=n;i++) sum[i]=sum[i-]+val[i];
for(int i=;i<=n;i++)
for(int j=i+;j<=n;j++)
dis[i][j]=dis[i][j-]+val[j]-val[i+j>>];
for(int i=;i<=n;i++) f[i][]=dis[][i];
int mn=<<,mnid;
for(int j=;j<=m;j++){
tran[n+][j]=n-;
for(int i=n;i>=j;i--){
for(int k=tran[i][j-];k<=tran[i+][j];k++){
if(f[k][j-]+dis[k+][i]<f[i][j]){
f[i][j]=f[k][j-]+dis[k+][i];
tran[i][j]=k;
}
}
}
}
cout<<f[n][m];
return ;
}