题解:P2803 学校选址 II

思路

不妨考虑使用最短路径(动态规划 + + + 递推)解决这个问题。

首先,设定第 1 1 1 个楼的位置作为坐标原点,第 i i i 个楼的位置表示为 d i d_i di。通过逻辑推理,我们可以得出,如果在 d i − 1 d_{i-1} di1 d i d_i di 中选择一个地点建立学校,那么最优的学校位置一定是这两个端点中的一个。具体地:

  • 当前 i − 1 i - 1 i1 个大楼的总学生数大于第 i i i n n n 个大楼的总学生数时,选择 d i d_i di 处建学校;
  • 如果小于,则选择 d i − 1 d_{i - 1} di1 处建学校;
  • 如果等于,两个点都可以作为学校的位置。
利用平面直角坐标系的知识

预处理一个二维数组 g i , j g_{i,j} gi,j,表示只考虑第 i i i 到第 j j j 个楼的学生时,放置学校的最优位置。

再定义一个动态规划数组 f i , k f_{i,k} fi,k,表示在前 i i i 个楼范围内建立 k k k 个学校时,可达到的最小总距离和。

  • k ≥ i k \geq i ki 时, f i , k = 0 f_{i,k} = 0 fi,k=0(即,学校数量足够多,可以每个楼都建一个学校,没有距离成本);
  • k = 1 k = 1 k=1 时, f i , k = g 1 , i f_{i,k} = g_{1,i} fi,k=g1,i(即,只建一个学校时,选择范围内最优位置);
  • 在其他情况下,考虑最后一个学校覆盖的楼房范围。如果是建在 d l d_l dl d i d_i di 之间,则最小总距离为 f l − 1 , k − 1 + g l , i f_{l-1, k-1} + g_{l, i} fl1,k1+gl,i

因此,动态规划的转移方程为:

f i , k = min ⁡ l = 1 i ( f l − 1 , k − 1 + g l , i ) f_{i,k} = \min_{l = 1}^{i} \left( f_{l-1, k-1} + g_{l, i} \right) fi,k=l=1mini(fl1,k1+gl,i)

最终结果即为 f n , K f_{n, K} fn,K,表示在所有楼中建立 K K K 个学校时的最小总距离和。


通过这种方式,我们可以系统地将问题分解为可管理的子问题,通过计算每个子问题的最优解并将这些解逐步合并,最终得到整个问题的最优解。

代码(有注释):

#include <iostream>
#include <cstring>

using namespace std;

const int N = 110; // 定义常量N作为楼房数量和学校数量的最大值
int n, K;          // n代表楼房的数量,K代表要建立的学校的数量
int dis[N];        // dis数组存储从第一个楼房到当前楼房的总距离
int g[N][N], f[N][N], w[N]; // g数组存放子问题最优情况下的最小总距离和
                            // f数组用于动态规划,记录考虑前i座楼房建j所学校的最小总距离和
                            // w数组存放每个楼房人数的前缀和

int main() {
  // 读入楼房数量和需要建立的学校数量
  scanf("%d%d", &n, &K);
  // 初始化第0座楼房的累计人数为0
  w[0] = 0;
  // 循环读入每座楼房的人数,并计算累计人数
  for (int i = 1; i <= n; i++) {
    int x;
    scanf("%d", &x);
    w[i] = w[i - 1] + x;
  }
  // 初始化第1座楼房的累计距离为0
  dis[1] = 0;
  // 循环读入相邻楼房之间的距离,并计算每座楼房的累计距离
  for (int i = 2; i <= n; i++) {
    int x;
    scanf("%d", &x);
    dis[i] = dis[i - 1] + x;
  }

  // 计算g数组中每个子问题的最优解
  for (int i = 1; i <= n; i++)
    for (int j = 1; j <= i; j++) {
      // 确定放置学校的最优位置
      int k;
      for (k = j; k <= i; k++)
        if (w[k] - w[j - 1] >= w[i] - w[k]) break;
      k = min(k, i);

      // 计算j到i所有楼房到学校k的距离和
      for (int l = j; l <= i; l++)
        g[j][i] += abs(dis[k] - dis[l]) * (w[l] - w[l - 1]);
    }

  // 初始化动态规划数组f,填充一个较大的数(表示距离无穷大)
  memset(f, 0x3f, sizeof f);
  // 动态规划计算至最多n座楼房,建立至多K座学校的最小总距离和
  for (int i = 1; i <= n; i++)
    for (int j = 1; j <= K; j++) {
      if (j >= i) f[i][j] = 0; // 学校数量不少于总楼房数,每座楼配一个学校,距离和为0
      else if (j == 1) f[i][j] = g[1][i]; // 只建一个学校的情况,距离和直接取g数组对应值
      else {
        // 枚举可能的学校位置,通过子问题的最优解更新当前问题的最小距离和
        for (int l = 1; l <= i; l++)
          f[i][j] = min(f[i][j], f[l - 1][j - 1] + g[l][i]);
      }
    }

  // 输出从1到n座楼房,建立K所学校的最小总距离和
  printf("%d\n", f[n][K]);
}
上一篇:使用 Django 构建简单 Web 应用


下一篇:echarts实现饼图见渐变