【題目描述】

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

【輸入】

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

2行為m?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。

【輸出】

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

【輸入樣例】

10 2
3 1 3 1 1 1 1 1 3

【輸出樣例】

18

【源程序】

#include<iostream> #include<cstring> #include<algorithm> using namespace std; int dis[510]; int a[510][510]; int dp[510][510]; int main() {int m,n;int i,j,k;memset(a,0,sizeof(a));cin>>m>>n;dis[1]=0;for(i=2;i<=m;i++){cin>>dis[i];dis[i]+=dis[i-1];}for(i=1;i<=m;i++)//學校建在i村j村的中間村落for(j=i+1;j<=m;j++)a[i][j]=a[i][j-1]+dis[j]-dis[(i+j)/2];for(i=1;i<=m;i++)for(j=1;j<=i&&j<=n;j++)dp[i][j]=9999999999;for(i=1;i<=m;i++)//dp[i][j]前i個村建j所學校,最短距離dp[i][1]=a[1][i];for(i=2;i<=m;i++)for(j=2;j<=i&&j<=n;j++)for(k=j-1;k<i;k++)dp[i][j]=min(dp[i][j],dp[k][j-1]+a[k+1][i]);cout<<dp[m][n]<<endl;return 0; }

?

新人創作打卡挑戰賽發博客就能抽獎！定制產品紅包拿不停！

總結

以上是生活随笔為你收集整理的山区建小学（信息学奥赛一本通-T1197）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。