山區建小學

題目描述

政府在某山區修建了一條道路，恰好穿越總共nn個村莊的每個村莊一次，沒有回路或交叉，任意兩個村莊只能通過這條路來往。已知任意兩個相鄰的村莊之間的距離為d_idi?（為正整數），其中，0<i<n0<i<n。為了提高山區的文化素質，政府又決定從nn個村中選擇mm個村建小學。請根據給定的nn、mm以及所有相鄰村莊的距離，選擇在哪些村莊建小學，才使得所有村到最近小學的距離總和最小，計算最小值。

輸入輸出格式

輸入格式：

?

第1行為n和m，其間用空格間隔。

第2行為n-1個整數，依次表示從一端到另一端的相鄰村莊的距離，整數之間以空格間隔。

例如

10 3

2 4 6 5 2 4 3 1 3

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

?

輸出格式：

?

各村莊到最近學校的距離之和的最小值。

?

輸入輸出樣例

輸入樣例#1：?復制

10 2
3 1 3 1 1 1 1 1 3

輸出樣例#1：?復制

18

說明

0 <?mm?<=?nn?< 500

0 <?d_idi??<=100

#include<bits/stdc++.h>
#define REP(i, a, b) for(int i = (a); i <= (b); ++ i)
#define REP(j, a, b) for(int j = (a); j <= (b); ++ j)
#define PER(i, a, b) for(int i = (a); i >= (b); -- i)
#define REP(k, a, b) for(int k = (a); k <= (b); ++ k)
using namespace std;
const int maxn=505;
template <class T>
inline void rd(T &ret){char c;ret = 0;while ((c = getchar()) < '0' || c > '9');while (c >= '0' && c <= '9'){ret = ret * 10 + (c - '0'), c = getchar();}
}
int n,m,dis[maxn],dp[maxn][maxn],w[maxn][maxn];
int main()
{rd(n),rd(m);REP(i,2,n)rd(dis[i]),dis[i]+=dis[i-1];REP(i,1,n){REP(j,i,n){int mid=i+j>>1;REP(k,i,j){w[i][j]+=abs(dis[mid]-dis[k]);}}}REP(i,0,n){REP(j,0,m){dp[i][j]=0x3f3f3f3f;}}dp[0][0]=0;REP(i,1,n){REP(j,1,m){if(j>i){dp[i][j]=0;continue;}REP(k,j-1,i){dp[i][j]=min(dp[i][j],dp[k][j-1]+w[k+1][i]);}}}cout<<dp[n][m]<<endl;return 0;
}

?