洛谷P2803:带权中位数的思考

带权中位数是CSP(NOIP)的一个常见问题。利用动态规划的方法寻找最佳落址。其中模板为邮局选址问题(post-office location problem)。这类问题有各种各样的衍生。这里我们讨论一道简单的变形:洛谷2803,小学生与小学选址。

原题目在洛谷P2803

数学特性

根据原题,虽然学校可以建在所有楼之间的任意一处,但可以证明,对于区间$[A, B]$中的一所小学,仅当小学位于某一楼的位置上,距离是最近的。这个假设可通过矛盾来证明。
假设在两栋楼的区间$[A, B]$,拥有学校P,将所有的学生连线到这所学校。向左移动的连线为方向,向右移动的连线为正向,总长度为$P$。楼$A$有$a$人,楼$B$有$b$人:

1
A --  --> B

设,有另一所小学在两栋楼之间,所有学生到该小学的总路程为$P’$。设这所小学从$A$出发,正向(向右)距离为$L$,则:

$$
P’ = P + L * a - L * b
$$

  • 若$a < b$,则必有向左移动到楼宇$A$,使得$P’$更小;
  • 若$a > b$,必有向右移动到楼宇$B$,使得$P’$更小;
  • $a = b$,不管移动到A或B,都不劣。

于是得到结论:对于楼宇区间$[A, B]$,仅当学校处在某一楼宇处,所得的距离最短。

推论

因为对于每个小学生,他们都需要走一定的路程到学校。对于拥有$a$人的楼$A$,到学校距离为$D$,所有小学生需要走的总路程为$a * D$。显然,我们可将每栋楼的小学生数量设置为该点的权值

假设学校建设在楼A,其加权距离为$P$。则可以通过此距离推算其他点的距离,以找到区间$[A, B]$间的最优解:

1
2
3
4
5
6
for (int mid = j + 1; mid <= i; mid++) {
// p for every position between A, B
p = p + distance(mid - 1, mid) * weight(mid - 1, j)
- distance(mid - 1, mid) * weight(i, mid);
if (min < p) min = p;
}

推论 2

根据上述代码,可知:当第一个位置,A到P人数>=P到B人数时,此处为最佳位置。(p最小)

代码过程

  1. 处理输入,累计各点的位置和权值。-> weight[i]dis[i]
    如:权值为:24,18,32
    则:累计为:24,42,74
    距离为:10, 8
    累计为:0, 10, 18

  2. 记忆化搜索任意楼宇区间$[i, j]$

    1. 找到区间i,j之间的权值中值
    2. 算这段区间的距离总长p
  3. 简单的背包问题改版,放学校 or 不放学校?

    1. 假设n栋楼配备了 >n 的学校,则距离为0
    2. 若n栋楼配备了1所学校,则跟2计算的结果相等
    3. 若对于区间$[a, b]$,算得最佳结果dp[a][b],且仅剩一所学校跟一个区间,则加上这个区间的最小权值中值

可得,这道题用了DP,首先搜索最佳位置,然后放学校。

代码

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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#define MAX 105

#define itn int

#define INF 0x7fffffff

int n, k;

int dis[MAX];

int weight[MAX];

int best_sit[MAX][MAX];

int dp[MAX][MAX];

// calculate the distance between buildings
int distance(int a, int b) { return abs(dis[a] - dis[b]); }

// calculate weight sum between buildings
int num(int a, int b) {
int i = a, j = b;
if (a > b) {
i = b;
j = a;
}
return weight[j] - weight[i - 1];
}

int main() {
using namespace std;
ios::sync_with_stdio();
cin >> n >> k;
memset(dp, 0, sizeof dp);
memset(dis, 0, sizeof dis);
memset(weight, 0, sizeof weight);
memset(best_sit, 0, sizeof best_sit);

for (int i = 1; i <= n; i++) {
int tmp;
cin >> tmp;
weight[i] = weight[i - 1] + tmp;
}

for (int i = 2; i <= n; i++) {
int tmp;
cin >> tmp;
dis[i] = dis[i - 1] + tmp;
}
int mid = 0;

// 算爆每个区间仅有一座学校的情况
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= i; j++) {
for (mid = j; mid <= i; mid++) {
if (num(j, mid) >= num(mid + 1, i)) break;
}

if (mid > i) mid = i;

int p = 0;
for (int l = j; l <= i; l++) {
p = p + distance(mid, l) * num(l, l);
}

best_sit[j][i] = p;
}
}

// 求 i 栋楼,j 所学校情况下的最优子结构
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= k; j++) {
if (j >= i)
dp[i][j] = 0;
else if (j == 1)
dp[i][j] = best_sit[1][i];
else {
int min = INF;

for (int l = 1; l <= i; l++) {
int tmp = dp[l - 1][j - 1] + best_sit[l][i];
if (tmp < min) min = tmp;
}
dp[i][j] = min;
}
}
}
cout << dp[n][k] << endl;
return 0;
}

评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×