P2803 学校选址 II

题目描述

在一条大路一旁有许多栋楼，每栋楼里有许多小学生。所以唯恐世界不乱的牛A打算在路上任选几点（可以和楼重合，当然也可以不重合）建立小学，且使所有小学生上学走的路程之和最短。牛A发现修建一所小学根本无法满足他唯恐世界不乱的心理，所以他准备建立K所小学。

输入格式

第一行2个整数，表示楼数n，学校数k（1<=n,k<=100）

第二行n个整数，表示每栋楼的学生数（0＜每栋楼学生数≤100 )

第三行n-1个数，分别表示楼i到楼i+1之间距离（1≤距离≤100，1≤i≤n-1）

输出格式

即学生走的距离和的最小值

解答

使用动态规划。“选 k 个点求最小代价”→ 想到找最优子结构→DP

定义DP状态：f[i][j]表示 “前 i 栋楼建 j 所小学的最小总路程”

则答案即为f[n-1][k] (从第0栋开始)

状态转移：考虑区间[0,i]内最后一所学校覆盖的范围，当覆盖的范围为[t+1,i]时，

f[i][j]=f[t][j-1] // 前t栋楼有j-1个学校

        +cost[t+1][i] // t+1至i有1个学校

cost[i][j]表示[i,j]区间有一所学校时的最小总路程。(子问题，关键！)

预处理cost数组

区间确定时，显然学校应建在一处使得：

• 左侧+这栋楼的学生数 >= 右侧学生数（否则学校移到右边那栋楼可使总距离减少） 且 右侧+这栋楼的学生数 >= 左侧学生数（同理）
• 即 第一个满足 左侧+这栋楼的学生数 >= 右侧学生数 的位置
• 即 第一个 左侧+这栋楼的学生数 >= 区间学生数的一半 的位置（可用lower_bound）

据此计算cost数组每一项，复杂度都为$O(n)$

AC代码

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

const int mm = 110;
int n, k, d[mm], s[mm];
int f[mm][mm], cost[mm][mm];

int main(){
    cin>>n>>k;

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

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

    for (int i=0; i<n; i++) {
        for (int j=0; j<n; j++) {
            if(i==j){
                cost[i][j]=0;
                continue;
            }
            int school=lower_bound(s+i+1, s+j+1, (s[j+1]+s[i])/2)-s-1;
            for (int l=i; l<=j; l++) {
                cost[i][j]+=(s[l+1]-s[l])*abs(d[l]-d[school]);
            }
        }
    }

    for (int i=0; i<n; i++) {
        for (int j=0; j<=k; j++) {
            f[i][j]=1e8;
        }
    }

    for (int i=0; i<n; i++) {
        f[i][1]=cost[0][i];
    }

    for (int i=2; i<=k; i++) {
        for (int j=i-1; j<n; j++) {
            for (int l=i-2; l<j; l++) {
                f[j][i]=min(f[j][i], f[l][i-1]+cost[l+1][j]);
            }
        }
    }

    cout<<f[n-1][k];
   
    return 0;
}