政府在某山区修建了一条道路，恰好穿越总共个村庄的每个村庄一次，没有回路或交叉，任意两个村庄只能通过这条路来往。已知任意两个相邻的村庄之间的距离为(为正整数)，其中，。为了提高山区的文化素质，政府又决定从个村中选择个村建小学(设。请根据给定的、以及所有相邻村庄的距离，选择在哪些村庄建小学，才使得所有村到最近小学的距离总和最小，计算最小值。
第1行为和，其间用空格间隔
第2行为 个整数，依次表示从一端到另一端的相邻村庄的距离，整数之间以空格间隔。
例如:
10 3 2 4 6 5 2 4 3 1 3
表示在个村庄建所学校。第个村庄与第个村庄距离为，第个村庄与第个村庄距离为，第个村庄与第个村庄距离为，...，第个村庄到第个村庄的距离为。
各村庄到最近学校的距离之和的最小值。
10 2 3 1 3 1 1 1 1 1 3
18
扫描二维码推送至手机访问。
版权声明：本文由青少年编程知识记录发布，如需转载请注明出处。
题目描述在一个拥有无限大小的二维平面的原点处，有一个舞蹈机器人，这个机器人将在这个平面上跳舞。这个机器人每次可以向自己的前方移动一个单位的长度，由于它需要在移动的过程中跳舞，因此，舞蹈机器人每移动一次...
【题目描述】一个旅行者有一个最多能装 m 公斤物品的背包，现在有 n 件物品，它们的重量分别是 w1,w2,…,wn, 它们的价值分别为 c1,c2,…cn 。若每种物品只有一件，求旅行者能获得的最大...
【题目描述】以 年-月-日 的形式给定一个日期，计算给定的日期是当年第几天。注意闰年二月有29天。【输入描述】输入格式为 yyyy-mm-dd，其中yyyy 表...
【题目描述】钟神近来编码劳累，想骑车风光一番，于是找某君骑自行车比赛。已知某君和钟神的每辆自行车的速度，钟神赢一场得50银两银子，输一场赔50银两，平局不挣也不赔。钟神可以随意安排高中低档自行车的出场...
【题目描述】这次童鞋们面临的问题是这样的：在一个平面内有两个点，求两个点分别和原点的连线的夹角的大小。注：夹角的范围[0，180]，两个点不会在圆心出现。【输入描述】输入数据的第一行是一个数据T，表示...
【题目描述】同学们下课后去食堂，每个人都需要一段时间去点菜。然而，某些同学点菜时间太长了。同学们对于等待很烦躁：他们希望，能尽量少的花时间等待。(同学数<=100000)，(0<=点菜耗时...