本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2022-02-05 19:11:48

题意：

题很简单，大意是给你 $n$ 个村庄的坐标（就一个数字），让你盖 $p$ 个邮局，问你怎么盖能让所有村庄到邮局的距离之和最小。

思路:

首先显然动态规划嘛O(∩_∩)O

数组 $f_{i,j}=i$ 个村庄时盖 $j$ 个镖局的答案。

【再建一个数组 $min$ （写代码的时候当然不能用这个名字）， $min_{i,j}=i$ 到 $j$ 这几个村庄如果只设一个镖局的答案，很显然应该放在中心，也就是 $(i+j)\div2$ 这里。】

---------状态转移方程分割线---------

1. $f_{i,j}=\min{f_{k,j-1}+min_{k+1,j}}$

很显然不用过多解释了吧（假的。

首先， $j$ 个镖局最少要有 $j$ 个村庄 (这不是废话吗)。

好，那么接下来，i个村庄j个镖局如果再加上 $x$ 个村庄这种方法是被允许的。

于是，$k$ 的范围应该在 $j-1$ 到 $i$ 之间。

2. $min_{i,j}=min_{i,j-1}+location_{j}-location_{(i+j)\div2}$

$location_{i}$ 是第 $i$ 个村庄的坐标。

这也不多说了，刚才说过了（详见用【】框起来的部分）

-----------50分代码-----------

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
int n , p , d[3005] , f[3005][305] , m[3005][3005];
int main(){
	scanf ("%d%d" , &n , &p);
	for(int i = 0; i < n; i ++)scanf ("%d" , &d[i]);
	for(int i = 0; i < n; i ++)
		for(int j = 0; j <= min(i , p - 1); j ++)
			f[i][j] = 0x3f3f3f3f;
	for(int i = 0; i < n; i ++){
		for(int j = i + 1; j < n; j ++)
			m[i][j] = m[i][j - 1] + d[j] - d[i + j >> 1];	
		f[i][0] = m[0][i];
	}
	for(int i = 1; i < n; i ++)
		for(int j = 1; j <= min(i , p - 1); j ++)
			for(int k = j - 1; k < i; k ++)
				f[i][j] = min(f[i][j] , f[k][j - 1] + m[k + 1][i]);
	printf ("%d" , f[n - 1][p - 1]);
	return 0;
}

但是这个程序的运算次数为 $30\times300\times300=27\times10^8=2.7\times10^9$，而现在一秒最多只能跑 $10^8$ 次，所以只能得 50 分。

但我们发现放邮局的地方是具有单调性的，因为如果放的再靠前的话他也不如放在后面好，所以我们可以用一个数组 $P_{i,j}$ 来记录，它代表前 $i$ 个村庄放第 $j$ 个邮局的地方，每次从 $P_{i,j-1}$ 开始枚举，因为他是有单调性的，所以可以从 $P_{i,j-1}$ 开始。

把这个加上的话，就可以去掉一些重复部分，所以可以过。

-----------AC 代码-----------

#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
const int INF = 0x3f3f3f3f , N = 3010 , M = 310;
int n , p;
int d[N];
int f[N][M] , g[N][N] , P[N][N];
int i , j , k;
int main(){
	scanf ("%d%d" , &n , &p);
	for(i = 0; i < n; ++ i)scanf ("%d" , &d[i]);
	for(i = 0; i < n; ++ i)
		for(j = 0; j <= min(i , p - 1); j ++)
			f[i][j] = INF;
	for(i = 0; i < n; ++ i){
		for(j = i + 1; j < n; ++ j)
			g[i][j] = g[i][j - 1] + d[j] - d[(i + j) \/ 2];	
		f[i][0] = g[0][i];
	}
	for(i = 1; i < n; ++ i)
		for(j = 1; j <= min(i , p - 1); ++ j) {
			for(k = P[i][j - 1]; k < i; ++ k) 
				if (f[i][j] > f[k][j - 1] + g[k + 1][i]) {
					f[i][j] = f[k][j - 1] + g[k + 1][i];
					P[i][j] = k;
				}
		}
	printf ("%d" , f[n - 1][p - 1]);
	return 0;
}