问题 5585 --[动归基础]邮局问题

5585: [动归基础]邮局问题

时间限制: 1 Sec  内存限制: 512 MB
提交: 12  解决: 8
[提交][状态][讨论版][数据上传:][下载FPS1元][添加到购物车][下载测试数据1元][84kb]

题目描述

邮局问题  post.pas

描述 Descrīption

     一些村庄建在一条笔直的高速公路边上,我们用一条坐标轴来描述这条公路,每个村庄的坐标都是整数,没有两个村庄的坐标相同。两个村庄的距离定义为坐标之差的绝对值。我们需要在某些村庄建立邮局。使每个村庄使用与它距离最近的邮局,建立邮局的原则是:所有村庄到各自使用的邮局的距离总和最小。

数据规模:1<=村庄数<=300,  1<=邮局数<=30,  1<=村庄坐标<=10000

输入格式 post.in

输入共2

第一行:n m {表示有n个村庄,建立m个邮局}

第二行:a1 a2 a3 .. an {表示n个村庄的坐标}

输出格式 post.out

1

第一行:S {表示最小距离总和}

样例输入

10 5

1 2 3 6 7 9 11 22 44 50

样例输出

9

来源 Source 

   IOI2000' 第五题

 

输入

输出

提示

来源

[提交][状态]