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) \right\} \]

其中， \(w(l,r)\) 表示区间 \(\left[ l,r \right]\) 中放一个邮局的贡献，由初中知识可知取最中间的村庄放置邮局一定最优。
那么就有：

\[w(l,r) = w(l,r-1) + X_{r} - X_{\lfloor \frac{l+r}{2} \rfloor} \]

显然， $ w $ 是满足四边形不等式和区间包含单调性的。

\[\text{设 } l_1 \le l_2 \le r_1 \le r_2 ,\\ \text{则 } w(l_1,r_1) + w(l_2,r_2) = \sum_{i=1}^{\lfloor \frac{l_1+r_1}{2} \rfloor} \left( X_{r_1-i+1} - X_{i} \right) + \sum_{i=1}^{\lfloor \frac{l_2+r_2}{2} \rfloor} \left( X_{r_2-i+1} - X_{i} \right) ,\\ w(l_1,r_2) + w(l_2,r_1) = \sum_{i=1}^{\lfloor \frac{l_1+r_2}{2} \rfloor} \left( X_{r_2-i+1} - X_{i} \right) + \sum_{i=1}^{\lfloor \frac{l_2+r_1}{2} \rfloor} \left( X_{r_1-i+1} - X_{i} \right) ,\\ \]

对比这两个式子，发现加的项和减的项数量都分别相同，观察项数的分配，发现，在第二个式子中，加的项更集中于靠近 \(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\n",f[n][m]);
	
	return 0;
}