政府在某山區(qū)修建了一條道路，恰好穿越總共m個村莊的每個村莊一次，沒有回路或交叉，任意兩個村莊只能通過這條路來往。已知任意兩個相鄰的村莊之間的距離為di(為正整數(shù))，其中，0<i<m。為了提高山區(qū)的文化素質(zhì)，政府又決定從m個村中選擇n個村建小學(xué)(設(shè)0<n≤m<500)。請根據(jù)給定的m、n以及所有相鄰村莊的距離，選擇在哪些村莊建小學(xué)，才使得所有村到最近小學(xué)的距離總和最小，計(jì)算最小值。

第1行為m和n，其間用空格間隔
第2行為m?1 個整數(shù)，依次表示從一端到另一端的相鄰村莊的距離，整數(shù)之間以空格間隔。
例如:
10 3
2 4 6 5 2 4 3 1 3

表示在10個村莊建3所學(xué)校。第1個村莊與第2個村莊距離為2，第2個村莊與第3個村莊距離為4，第3個村莊與第4個村莊距離為6，...，第9個村莊到第10個村莊的距離為3。

零基礎(chǔ)同學(xué)可以先學(xué)習(xí)視頻課程，包含C/C++、Python、百練、藍(lán)橋杯輔導(dǎo)、算法數(shù)據(jù)結(jié)構(gòu)等課程，提供視頻講解以及配套習(xí)題，還有老師答疑，點(diǎn)擊這里了解課程詳情

編程練習(xí) 遞推 基礎(chǔ)