邮局

高速公路旁边有一些村庄。高速公路表示为整数轴，每个村庄的位置用单个整数坐标标识。没有两个在同样地方的村庄。两个位置之间的距离是其整数坐标差的绝对值。

邮局将建在一些，但不一定是所有的村庄中。为了建立邮局，应选择他们建造的位置，使每个村庄与其最近的邮局之间的距离总和最小。

你要编写一个程序，已知村庄的位置和邮局的数量，计算每个村庄和最近的邮局之间所有距离的最小可能的总和。

\(n\leq 3000,m\leq 300\)。

双重四边形不等式

https://blog.csdn.net/a_forever_dream/article/details/105554850

设\(f(i,j)\)表示前\(i\)个村庄建了\(j\)个邮局的最小代价。

\[f(i,j)=\min_{k< i}\{f(k,j-1)+w(k+1,i)\} \]

其中\(w(l,r)\)表示给区间\([l,r]\)里的村庄建个邮局的最小代价。显然邮局应该摆在中位数的位置（链上带权重心）。

然后可以证明\(w\)满足四边形不等式。接着可以证明\(f\)满足四边形不等式。其实这两个应该目测或者打表发现。

证明一下最优决策点的优化\(p(i,j-1)\leq p(i,j)\leq p(i+1,j)\)。

\(p(i,j-1)\leq p(i,j)\)

令\(p=p(i,j),p< q\)，考虑\(f(i,j-1)\)的转移\(f(i,j-1)\xleftarrow{q}f(q,j-2)+w(q+1,i)\)，\(f(i,j-1)\xleftarrow{p}f(p,j-2)+w(p+1,i)\)。

做个差，我们就只需要证明\(f(q,j-2)+w(q+1,i)-f(p,j-2)-w(p+1,i)\geq 0\)

再考虑\(f(i,j)\)的转移\(f(i,j)\xleftarrow{q}f(q,j-1)+w(q+1,i)\)，\(f(i,j)\xleftarrow{p}f(p,j-1)+w(p+1,i)\)。

做个差，我们就得到条件\(f(q,j-1)+w(q+1,i)-f(p,j-1)-w(p+1,i)\geq 0\)。

注意到\(w(q+1,i)\)和\(w(p+1,i)\)在两个不等式中都出现了，所以\(f(q,j-1)+w(q+1,i)-f(p,j-1)-w(p+1,i)\geq f(q,j-2)-f(p,j-2)+f(p,j-1)-f(q,j-1)\geq 0\)。

\(p(i,j)\leq p(i+1,j)\)

令\(p=p(i,j),q< p\)，考虑\(f(i+1,j)\)的转移\(f(i+1,j)\xleftarrow{q}f(q,j-1)+w(q+1,i+1)\)，\(f(i+1,j)\xleftarrow{p}f(p,j-1)+w(p+1,i+1)\)。

做个差，我们就只需要证明\(f(q,j-1)+w(q+1,i+1)-f(p,j-1)-w(p+1,i+1)\geq 0\)。

再考虑\(f(i,j)\)的转移\(f(i,j)\xleftarrow{q}f(q,j-1)+w(q+1,i)\)，\(f(i,j)\xleftarrow{p}f(p,j-1)+w(p+1,i)\)。

做个差，我们就得到条件\(f(q,j-1)+w(q+1,i)-f(p,j-1)-w(p+1,i)\geq 0\)。

注意到\(f(q,j-1)\)和\(f(p,j-1)\)在两个不等式中都出现了，所以\(f(q,j-1)+w(q+1,i+1)-f(p,j-1)-w(p+1,i+1)\geq w(q+1,i+1)-w(p+1,i+1)+w(p+1,i)-w(q+1,i)\geq 0\)。

那么就用结论优化DP就好了。时间复杂度\(O(nm)\)。

CO int N=3e3+10;
int a[N],s[N];
int f[N][N],p[N][N];

IN int w(int l,int r){
	int mid=(l+r)>>1;
	return s[r]-s[mid]-a[mid]*(r-mid)+a[mid]*(mid-l)-(s[mid-1]-s[l-1]);
}
int main(){
	int n=read<int>(),m=read<int>();
	for(int i=1;i<=n;++i) s[i]=s[i-1]+read(a[i]);
	for(int i=1;i<=n;++i) f[i][1]=w(1,i);
	for(int j=2;j<=m;++j){
		p[n+1][j]=n;
		for(int i=n;i>=1;--i){
			f[i][j]=1e9;
			for(int k=p[i][j-1];k<=p[i+1][j];++k)
				if(f[k][j-1]+w(k+1,i)<f[i][j])
					f[i][j]=f[k][j-1]+w(k+1,i),p[i][j]=k;
		}
	}
	printf("%d\n",f[n][m]);
	return 0;
}

四边形不等式+带权二分

https://blog.csdn.net/a_forever_dream/article/details/105587292

目测或打表容易得到，函数是凸的。换句话说，随着邮局数量的增加，代价在减小，但是减小的量在逐渐变少。

那么用带权二分去切凸包即可。

时间复杂度\(O(n\log n\log a)\)。

CO int N=3e3+10,inf=1e3;
int a[N],s[N];

IN int calc(int l,int r){
	if(l>r) return inf;
	int mid=(l+r)/2;
	return a[mid]*(mid-l)-(s[mid-1]-s[l-1])+s[r]-s[mid]-a[mid]*(r-mid);
}

struct value {int w,c;} f[N];

IN bool operator<(CO value&a,CO value&b){
	return a.w!=b.w?a.w<b.w:a.c<b.c; // as few as possible
}
IN value operator+(CO value&a,CO value&b){
	return {a.w+b.w,a.c+b.c};
}

int solve(int n,int mid){
	struct node {int l,r,i;};
	deque<node> que={{1,n,0}};
	for(int i=1;i<=n;++i){
		for(;que.front().r<i;que.pop_front());
		f[i]=f[que.front().i]+(value){calc(que.front().i+1,i)+mid,1};
		for(;f[i]+(value){calc(i+1,que.back().l),1}<f[que.back().i]+(value){calc(que.back().i+1,que.back().l),1};que.pop_back());
		if(f[i]+(value){calc(i+1,que.back().r),1}<f[que.back().i]+(value){calc(que.back().i+1,que.back().r),1}){
			int l=que.back().l,r=que.back().r;
			while(l<r){
				int mid=(l+r)>>1;
				f[i]+(value){calc(i+1,mid),1}<f[que.back().i]+(value){calc(que.back().i+1,mid),1}?r=mid:l=mid+1;
			}
			que.back().r=l-1;
			que.push_back({l,n,i});
		}
		else que.push_back({que.back().r+1,n,i});
	}
	return f[n].c;
}
int main(){
	int n=read<int>(),m=read<int>();
	for(int i=1;i<=n;++i) s[i]=s[i-1]+read(a[i]);
	int l=0,r=1e4;
	while(l<r){
		int64 mid=(l+r)>>1;
		solve(n,mid)<=m?r=mid:l=mid+1;
	}
	solve(n,l);
	printf("%d\n",f[n].w-l*m);
	return 0;
}