题目地址：

题目描述： 在一条大路一旁有许多栋楼，每栋楼里有许多小学生（哈哈哈一波小学生来袭！）。但是这条路上没有小学！！！！所以唯恐世界不乱的牛A打算在路上（汽车什么的都不敢来这个小学生云集的地方咯，所以不用担心安全问题）任选几点（可以和楼重合，当然也可以不重合）建立小学，且使所有小学生上学走的路程之和最短。牛A发现修建一所小学根本无法满足他唯恐世界不乱的（变态）心理，所以他准备建立 K K K所小学。

输入格式： 第一行 2 2 2个整数，表示楼数 n n n，学校数 k k k（ 1 ≤ n , k ≤ 100 1le n,kle 100 1≤n,k≤100） 第二行 n n n个整数，表示每栋楼的学生数（ 0 ＜ 0＜ 0＜每栋楼学生数 ≤ 100 ≤100 ≤100） 第三行 n − 1 n-1 n−1个数，分别表示楼 i i i到楼 i + 1 i+1 i+1之间距离（ 1 ≤ 1≤ 1≤距离 ≤ 100 ≤100 ≤100， 1 ≤ i ≤ n − 1 1≤i≤n-1 1≤i≤n−1）

输出格式： 即学生走的距离和的最小值

以第 1 1 1个楼的位置作为坐标原点，设第 i i i个楼的位置为 d [ i ] d[i] d[i]。容易证明，如果要在 [ d [ i − 1 ] , d [ i ] ] [d[i-1],d[i]] [d[i−1],d[i]]中选一个地方放学校，则该学校最优位置一定是两个端点其一处。当前 i − 1 i-1 i−1个大楼的总学生数大于第 i i i到 n n n个大楼的总学生数的时候，显然要选 d [ i ] d[i] d[i]处建学校；如果小于，则在 d [ i − 1 ] d[i-1] d[i−1]处建学校；如果等于，则两个点都可以。

我们可以预处理一个二维数组 g [ i ] [ j ] g[i][j] g[i][j]，表示只考虑第 i ∼ j isim j i∼j的楼的学生的时候，最优的放置学校的位置。 g g g是很容易求出的。再定义 f [ i ] [ k ] f[i][k] f[i][k]为在前 i i i个楼的范围内建 k k k个学校的情况下，最小的总距离和是多少。那么，如果 k ≥ i kge i k≥i，则 f [ i ] [ k ] = 0 f[i][k]=0 f[i][k]=0；如果 k = 1 k=1 k=1，即只建一个学校，则根据定义， f [ i ] [ k ] = g [ 1 ] [ i ] f[i][k]=g[1][i] f[i][k]=g[1][i]；剩余情况，可以按最右边的那个学校服务哪些楼的学生来分类，如果是建在 d [ l ] ∼ d [ i ] d[l]sim d[i] d[l]∼d[i]之间（并且也服务这些学生），那么最小总距离为 f [ l − 1 ] [ k − 1 ] + g [ l ] [ i ] f[l-1][k-1]+g[l][i] f[l−1][k−1]+g[l][i]，所以： f [ i ] [ k ] = min ⁡ l = 1 , 2 , . . . , i f [ l − 1 ] [ k − 1 ] + g [ l ] [ i ] f[i][k]=min_{l=1,2,...,i} f[l-1][k-1]+g[l][i] f[i][k]=l=1,2,...,iminf[l−1][k−1]+g[l][i]最后返回 f [ n ] [ k ] f[n][k] f[n][k]即可。代码如下：

#include <iostream>
#include <cstring>
using namespace std;

const int N = 110;
int n, K;
int dis[N];
int g[N][N], f[N][N], w[N];

int main() {
          
   
  scanf("%d%d", &n, &K);
  for (int i = 1; i <= n; i++) {
          
   
    int x;
    scanf("%d", &x);
    w[i] = w[i - 1] + x;
  }
  for (int i = 2; i <= n; i++) {
          
   
    int x;
    scanf("%d", &x);
    dis[i] = dis[i - 1] + x;
  }

  for (int i = 1; i <= n; i++)
    for (int j = 1; j <= i; j++) {
          
   
      // 找到只考虑第j到第i个楼的情况下，学校放哪里总距离和最小
      int k;
      for (k = j; k <= i; k++)
        if (w[k] - w[j - 1] >= w[i] - w[k]) break;
      k = min(k, i);

      for (int l = j; l <= i; l++)
        g[j][i] += abs(dis[k] - dis[l]) * (w[l] - w[l - 1]);
    }

  memset(f, 0x3f, sizeof f);
  for (int i = 1; i <= n; i++)
    for (int j = 1; j <= K; j++) {
          
   
      if (j >= i) f[i][j] = 0;
      else if (j == 1) f[i][j] = g[1][i];
      else {
          
   
        for (int l = 1; l <= i; l++)
          f[i][j] = min(f[i][j], f[l - 1][j - 1] + g[l][i]);
      }
    }

  printf("%d
", f[n][K]);
}

时间复杂度 O ( n 2 ( n + k ) ) O(n^2(n+k)) O(n2(n+k))，空间 O ( n ( n + k ) ) O(n(n+k)) O(n(n+k))。