最新公告
  • 欢迎您光临信息学奥赛网,一个优质的信息学编程题库和信息学编程学习资源专业网站。欢迎加入VIP
  • 山区建小学

    正文概述 陈老师   2026-01-20 15:30:10  

    题目描述

    政府在某山区修建了一条道路,恰好穿越总共 mm 个村庄的每个村庄一次,没有回路或交叉,任意两个村庄只能通过这条路来往。

    已知任意两个相邻的村庄之间的距离为 did_i (为正整数),其中, 0<i<m0 < i < m 。为了提高山区的文化素质,政府又决定从 mm 个村中选择 nn 个村建小学(设 0<n≤m<5000 < n ≤ m < 500 )。

    请根据给定的 mm 、 nn 以及所有相邻村庄的距离,选择在哪些村庄建小学,才使得所有村到最近小学的距离总和最小,计算最小值。

    输入

    第1行为 mm 和 nn ,其间用空格间隔

    第2行为 m−1m-1 个整数,依次表示从一端到另一端的相邻村庄的距离,整数之间以空格间隔。

    例如:

    10 3
    2 4 6 5 2 4 3 1 3
    

    表示在 1010 个村庄建 33 所学校。第 11 个村庄与第 22 个村庄距离为 22 ,第 22 个村庄与第 33 个村庄距离为 44 ,第 33 个村庄与第 44 个村庄距离为 66 ,...,第 99 个村庄到第 1010 个村庄的距离为 33 。

    输出

    各村庄到最近学校的距离之和的最小值。

    样例

    10 2
    3 1 3 1 1 1 1 1 3
    
    18
    
    信息学奥赛网,一个优质的信息学奥赛学习资源平台!
    信息学奥赛网 » 山区建小学