post_office问题

发表于 | Edited on | 分类于 | 次阅读

Post Office 修建问题。

地址： http://noi.openjudge.cn/ch0206/162/

解题思路

设置F[p][v]表示V个village中修建p个邮局使得所有村庄到最近邮局的距离最近。
得到了如下递推公式：
F[p][v] = min{F[p][v], F[p-1][k-1]+ dis[k][v]};
为什么这样进行递推？这是因为本题目中以最后一个邮局所属的村庄进行划分，因为总有一些village到最后一个邮局的距离是最近的，但是这些村子的数量不知道，我们需要知道到底多少village划归到最后一个post office的时候是最优的。

#####隐藏内容
但是我们知道，能够划分到最后一个post office的village，至少是第p个，修建之前的p-1个post office，至少需要p-1个village。因此有如下等式：

p-1<=k-1<=v

递推式表示在前面k-1个village中修建p-1个post office，随后的第k个village到第v个village，修建最后一个post office， dis[k][v]表示在第k个village和第v个village中修建1个post office时各个village到这个post office的距离之和的最小值。

现在需要解决如下问题，dis[k][v]如何计算？
在k和v之间修建一个post office，同时所有village到该post office的距离最小，该如何计算呢？正确计算方法是将post office修建到这些village的中位数中。

假设范围是i和j-1之间的中位数中修建了一个post office，最优值为dis[i][j-1],现在当新加入一个village j之后。假设i和j-1之间的中位数是K，新加入j之后选择L作为新的post office 位置。现在分情况讨论：

  • 如果原本i和j之间有奇数个village，新加入一个j之后，仍然可以取原来的K作为中位数，此时中位数位置不变，所以
    dis[i,j] = dis[i,j-1]+village[j] - village[(j+i)/2]
  • 如果原本i和j之间有偶数个village，假设此时post office的修建地址设置为中位数中较大的数的位置，此时新加入j后，post office的位置不发生改变，那么仍然由如下计算公式：
    dis[i,j] = dis[i,j-1]+village[j] - village[(j+i)/2]

综上，可以得出:


dis[i,j] = dis[i,j-1]+village[j] - village[(j+i)/2]

源代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include<cstdio>
#include<vector>
#include<cmath>
#include<algorithm>
#include<climits>
using namespace std;

int solution(vector<int>& village, int officeCount) {
	vector<vector<int>> F(officeCount + 1, vector<int>(village.size(), 0));
	vector<vector<int>> dis(village.size(), vector<int>(village.size(), 0));
	for (int i = 1; i < village.size(); ++i){
		for (int j = i+1; j < village.size(); ++j) {
			int k1 = (i + j - 1) >> 1;
			int  k2 = (i + j) >> 1;
			dis[i][j] = dis[i][j - 1] + village[j] - village[(i+j)/2];
		}
	}
	for (int v = 1; v < village.size(); ++v)
		F[1][v] = dis[1][v];

	for (int p = 2; p <= officeCount; ++p){
		for (int v = p; v < village.size(); ++v) {
			F[p][v] = INT_MAX;
			for (int k = p; k <=v; ++k)
				F[p][v] = min(F[p][v],F[p-1][k-1]+dis[k][v]);
		}
	}
	return F[officeCount][village.size() - 1];
}



int main() {
	int V, P;
	while (scanf("%d %d", &V, &P) != EOF) {	
		vector<int> village(V+1, 0);
		for (int i = 1; i <= V; ++i)
			scanf("%d", &village[i]);
		printf("%d\n",solution(village, P));
	
	}
}

时间复杂度

上述代码的时间复杂度为O(pV^2)