问题 4480 --5-打井

4480: 5-打井

题目描述

  阿什尼又双叒叕沉迷了一个新的小游戏.这是一个类似于模拟人生的游戏,只不过里面的角色都是史莱姆.

在一条笔直的沙漠道路的两旁生坐落着数个沙漠史莱姆部落.为了解决吃水的问题,阿什尼需要在n个部落里选m个部落来打水井.现在你知道了所有的相邻部落的距离,问选择哪些村庄打水井,使得所有部落到最近水井的距离最小?

输入

第1行为n和m，其间用空格间隔
第2行为m-1个整数，依次表示从一端到另一端的相邻部落的距离，整数之间以空格间隔。

输出

各部落到最近水井的距离之和的最小值

样例输入输出

输入#1 复制 
10 2
3 1 3 1 1 1 1 1 3
输出#1 复制 
18

提示

0 < m ≤ n  ≤ 500

发表题解
序号 标题 作者 发表时间 费用 订购数 操作

题目信息

提交
难度
普及+/提高-
标签
点击显示
递交数
9
已通过
4
通过率
45%
时间限制
1 秒
内存限制
128 MB
来源
2019北京东城(初中)
收藏