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

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

原题目在洛谷P2803。

数学特性

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

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]$间的最优解：

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，首先搜索最佳位置，然后放学校。

代码

#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;
}