2771 - 全民健身
题目描述
A 市有一条笔直的国道，国道会经过 M 个小区。已知任意两个相邻的小区的距离为 d_i（0 \lt d_i \le 200)。
为响应市里全民健身的号召，市里准备在这 M 个小区中，选择 N 个小区安装健身器材（1 \le N \le M \lt 500）。
请编程计算出，选择哪些小区安装健身器材，才能使得所有小区到最近的有健身器材的小区锻炼身体的距离总和最小，你只需要计算并输出这个最小值就可以。
输入
第 1 行有两个整数 M 和 N；
第 2 行有 M-1个整数，表示沿着国道从一端到另一端，相邻的 2 个小区的距离。
输出
各小区到最近的有健身器材小区要走的距离和的最小值。
样例
输入
4 1 1 2 3
输出
8
输入
10 2 3 1 3 1 1 1 1 1 3
输出
18
说明
样例 1 解释
国道沿线经过 4 个小区，需要选 1 个小区安装健身器材。
第 1 个小区到第 2 个小区的距离为 1，第 2 个小区到第 3 个小区的距离为 2，第 3 个小区到第 4 个小区的距离为 3。
在该样例中，选第 2 个小区安装健身器材，其他小区的人要走过来需要走的距离和最小，距离和=1+2+5=8，如果选第 3 个小区安装健身器材，需要走的距离和也是最小的。
标签
