UC知道C++一道邮局问题，高手来
来源：百度知道 编辑：UC知道 时间：2024/06/22 19:22:00
一些村庄建在一条笔直的高速公路边上。我们用一条坐标轴来描述这条高速公路，每一个村庄的坐标都是整数。没有两个村庄坐标相同。两个村庄间的距离，定义为它们坐标值差的绝对值。我们需要在一些村庄建立邮局——当然，并不是每一个村庄都必须建立邮局，邮局必须建立在村庄里，因此它的坐标和它所在的村庄坐标相同。每个村庄使用离它最近的邮局，建立邮局的原则的：所有村庄到各自所使用的邮局的距离总和最小。
你的任务是编写一个程序，在给定了每个村庄的坐标轴和将要建立的邮局数之后，按照上述原则，合理地选择这些邮局的位置。
输入
输入文件的文件名是POST.IN
文件的第一行包含两个整数，第一个整数是村庄的数目V，1<=V<=300,第二个整数是将建立的邮局数P,1<=P<=30且P<=V,
文件的第二行递增顺序列出了V个整数。这V个整数分别表示各个村庄的位置坐标，对于每一个位置坐标x,1<=x<=10000。
输出
输出文件名是POST.OUT
文件的第一行是一个整数S，表示你所求出的所有村庄到离它最近邮局的距离的总和。
相应地，文件的第二行按照递增顺序列出了P个整数，分别表示你所求出的每个邮局的建立位置。虽然对于同一个S，可能会有多种邮局建立的方案，但只需输出其中的一种。
输入输出示例
输入文件（POST.in）
10 5
1 2 3 6 7 9 11 22 44 50
输出文件名 POST.OUT
9
2 7 22 44 50
请用标准的可以过DEVC++的C++语言编写
谢谢~~！！！！！！！！！！！！！！！！！
你的任务是编写一个程序，在给定了每个村庄的坐标轴和将要建立的邮局数之后，按照上述原则，合理地选择这些邮局的位置。
输入
输入文件的文件名是POST.IN
文件的第一行包含两个整数，第一个整数是村庄的数目V，1<=V<=300,第二个整数是将建立的邮局数P,1<=P<=30且P<=V,
文件的第二行递增顺序列出了V个整数。这V个整数分别表示各个村庄的位置坐标，对于每一个位置坐标x,1<=x<=10000。
输出
输出文件名是POST.OUT
文件的第一行是一个整数S，表示你所求出的所有村庄到离它最近邮局的距离的总和。
相应地，文件的第二行按照递增顺序列出了P个整数，分别表示你所求出的每个邮局的建立位置。虽然对于同一个S，可能会有多种邮局建立的方案，但只需输出其中的一种。
输入输出示例
输入文件（POST.in）
10 5
1 2 3 6 7 9 11 22 44 50
输出文件名 POST.OUT
9
2 7 22 44 50
请用标准的可以过DEVC++的C++语言编写
谢谢~~！！！！！！！！！！！！！！！！！
给，在VC++6.0环境上已经编译运行确认：
#include<cstdio>
#include<cstdlib>
#define Int_Max 1000000
int n,m,i,j,s[301][301]={0},dp[301][31],map[301],t,h,k;
int main()
{
freopen("POST.in","r",stdin);
freopen("POST.OUT","w",stdout);
scanf("%d%d",&n,&m);
for(i=1;i<=n;i++) scanf("%d",&map[i]);
for(i=0;i<=n;i++) for(j=0;j<=m;j++) dp[i][j]=Int_Max;
for(i=1;i<=n;i++)
for(j=i;j<=n;j++){
s[i][j]=0;
t=(i+j)/2;
for(h=i;h<=j;h++) s[i][j]+=abs(map[h]-map[t]);
}
for (i=1;i<=n;i++) dp[i][1]=s[1][i];
for(j=2;j<=m;j++)
for(i=j;i<=n;i++)
for(k=j-1;k<i;k++)if((dp[k][j-1]+s[k+1][i])<dp[i][j]) dp[i][j]=dp[k][j-1]+s[k+1][i];
printf("%d\n",dp[n][m]);
return 1;
}