P4767「IOI2000」邮局
显然 DP ，考虑设 (f_{i,j}) 表示前 (j) 个村庄放了 (i) 个邮局的最小距离，为了方便 DP ，我们钦定这个区间里的村庄都匹配这些邮局。
那么转移式写出来就是 ：
[f_{i,j} = min_{k=1}^{j-1} left{ f_{i,k-1} + w(k+1,j)
ight}
]
其中， (w(l,r)) 表示区间 (left[ l,r
ight]) 中放一个邮局的贡献，由初中知识可知取最中间的村庄放置邮局一定最优。
那么就有：
[w(l,r) = w(l,r-1) + X_{r} - X_{lfloor frac{l+r}{2}
floor}
]
显然， $ w $ 是满足四边形不等式和区间包含单调性的。
[ ext{设 } l_1 le l_2 le r_1 le r_2 ,\
ext{则 } w(l_1,r_1) + w(l_2,r_2) = sum_{i=1}^{lfloor frac{l_1+r_1}{2}
floor} left( X_{r_1-i+1} - X_{i}
ight) +
sum_{i=1}^{lfloor frac{l_2+r_2}{2}
floor} left( X_{r_2-i+1} - X_{i}
ight) ,\
w(l_1,r_2) + w(l_2,r_1) = sum_{i=1}^{lfloor frac{l_1+r_2}{2}
floor} left( X_{r_2-i+1} - X_{i}
ight) +
sum_{i=1}^{lfloor frac{l_2+r_1}{2}
floor} left( X_{r_1-i+1} - X_{i}
ight) ,\
]
对比这两个式子，发现加的项和减的项数量都分别相同，观察项数的分配，发现，在第二个式子中，加的项更集中于靠近 (r_2) ，减的项更集中于 (l_1) ，所以符合四边形不等式。
然后 ，根据套路 (g_{i-1,j} le g_{i,j} le g_{i,j+1}) ，倒序跑 DP 即可，时间复杂度 (O(VP)) 。
其中 (g_{i,j}) 表示 (f_{i,j}) 的最小最优决策点。
#include<bits/stdc++.h>
#define fo(i,a,b) for(int i=a;i<=b;++i)
#define fd(i,a,b) for(int i=a;i>=b;--i)
using namespace std;
const int N=3010;
const int M=310;
int f[N][M],n,m,w[N],g[N][N],fr[N][M];
bool cmp(int a,int b){return a<b;}
int main(){
scanf("%d%d",&n,&m);
fo(i,1,n)scanf("%d",&w[i]);
sort(w+1,w+n+1,cmp);
fo(i,1,n){
fo(j,i+1,n)
g[i][j]=g[i][j-1] + w[j] - w[(i+j)/2];
}
memset(f,127,sizeof(f));
f[0][0]=0;
fo(j,1,m){
fr[n+1][j]=n;
fd(i,n,1){
fo(r,fr[i][j-1],fr[i+1][j]){
int tmp=f[r][j-1] + g[r+1][i];
if(tmp<f[i][j]){
f[i][j]=tmp;
fr[i][j]=r;
}
}
}
}
printf("%d
",f[n][m]);
return 0;
}