题目链接

\(Description\)

一条直线上有n个村庄，位置各不相同。选择p个村庄建邮局，求每个村庄到最近邮局的距离之和的最小值。

\(Solution\)

先考虑在\([l,r]\)建一个邮局，最优解肯定是建在中间。

这样\(mid\)两边对称，距离和是最小的；若建在\(mid-1\)，(假设\(mid\)与\(mid-1\)相距\(1\))虽然左边\(mid-1\)个村庄\(dis\)都\(-1\)了，但是右边有\(mid\)个村庄的\(dis\)会\(+1\)。

如果区间长度为偶数，建在中间两个位置任意一个都是最优的。

设\(f[i][j]\)表示在前\(i\)个村庄建了\(j\)个邮局的最小值，那么 \(f[i][j] = \min\{ f[k][j-1]+dis(k+1,i) \}\)。

\(dis(k+1,i)\)表示只考虑在\([k+1,i]\)建一个邮局的最小值。

预处理\(dis\)时 如果已知\(dis[i][j-1]\)，那么无论\(j-1\)是奇是偶，\(dis[i][j]\)都等于\(dis[i][j-1]+ j到i~j中点的距离\)(也可以算出来吧)

另外满足决策单调性\(P[i][j-1]\leq P[i][j]\leq P[i+1][j]\)，能用四边形不等式优化到\(O(np)\)

于是从0ms优化到了16ms??同样0ms了

[Update]：这题好像还可以带权二分。。

#include <cstdio>

#include <cctype>

#include <cstring>

#include <algorithm>

#define gc() getchar()

const int N=305;

int n,m,A[N],f[N][35],dis[N][N],P[N][N];

inline int read()

{

	int now=0;register char c=gc();

	for(;!isdigit(c);c=gc());

	for(;isdigit(c);now=now*10+c-'0',c=gc());

	return now;

}

void DP1()//O(n^2m)

{

	for(int i=1; i<=n; ++i)

		for(int j=2; j<=m; ++j)//from 2

			for(int k=j-1; k<i; ++k)

				f[i][j]=std::min(f[i][j],f[k][j-1]+dis[k+1][i]);

}

void DP2()//O(nm)

{

	for(int tmp,j=2; j<=m; ++j)//先枚举j吧 (不知道为什么先i不对==)

	{

		P[n+1][j]=n-1;//上边界！

		for(int i=n; i>=j; --i)

			for(int k=P[i][j-1]; k<=P[i+1][j]; ++k)

				if(f[i][j]>(tmp=f[k][j-1]+dis[k+1][i]))

					f[i][j]=tmp, P[i][j]=k;

	}

}

int main()

{

	n=read(),m=read();

	for(int i=1; i<=n; ++i) A[i]=read();

	for(int i=1; i<n; ++i)

		for(int j=i+1; j<=n; ++j)

			dis[i][j]=dis[i][j-1]+A[j]-A[i+j>>1];

	memset(f,0x3f,sizeof f);

	for(int i=1; i<=n; ++i) f[i][1]=dis[1][i] ,P[i][i]=i;//预处理！

	DP2();

	printf("%d",f[n][m]);

	return 0;

}