思路
不妨考虑使用最短路径(动态规划 + + + 递推)解决这个问题。
首先,设定第 1 1 1 个楼的位置作为坐标原点,第 i i i 个楼的位置表示为 d i d_i di。通过逻辑推理,我们可以得出,如果在 d i − 1 d_{i-1} di−1 和 d i d_i di 中选择一个地点建立学校,那么最优的学校位置一定是这两个端点中的一个。具体地:
- 当前 i − 1 i - 1 i−1 个大楼的总学生数大于第 i i i 到 n n n 个大楼的总学生数时,选择 d i d_i di 处建学校;
- 如果小于,则选择 d i − 1 d_{i - 1} di−1 处建学校;
- 如果等于,两个点都可以作为学校的位置。
利用平面直角坐标系的知识
预处理一个二维数组 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 k≥i 时, 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} fl−1,k−1+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(fl−1,k−1+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]);
}