题目描述

政府在某山区修建了一条道路，恰好穿越总共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 23 1 3 1 1 1 1 1 3

输出样例#1： 

18

说明

0 < mm <= nn < 500

0 < d_idi​ <=100

#include
     
      #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 
      
       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<
       
        <