UC知道pascal 信息学奥赛 动态规划基础题 邮局问题
来源：百度知道 编辑：UC知道 时间：2024/09/22 19:39:58
描述 Description
一些村庄建在一条笔直的高速公路边上，我们用一条坐标轴来描述这条公路，每个村庄的坐标都是整数，没有两个村庄的坐标相同。两个村庄的距离定义为坐标之差的绝对值。我们需要在某些村庄建立邮局。使每个村庄使用与它距离最近的邮局，建立邮局的原则是：所有村庄到各自使用的邮局的距离总和最小。
数据规模：1<=村庄数<=300, 1<=邮局数<=30, 1<=村庄坐标<=10000
输入格式 Input Format
2行
第一行:n m {表示有n个村庄，建立m个邮局}
第二行:a1 a2 a3 .. an {表示n个村庄的坐标}
输出格式 Output Format
1行
第一行:l {l表示最小距离总和}
var
max:Array[1..300,1..30] of integer;
map:array[0..300] of integer;
i,j,n,k,il,l,all:integer;
function con(a,b:integer):integer;
begin
con:=0;
while a<b do
begin
inc(con,map[b]-map[a]);
inc(a);
dec(b);
end;
end;
begin
第一 ：il的循环应该是从i开始而不是i-1，因为可以只管1个村庄；
第二 ：原题坐标比较大，用integer无法保存，应改为longint；
（但数据太弱，所以integer也可以过。。。）
第三 ：如果用integer，max[i,j]的初值也为maxint的话，后面的max[il-1,j-1]+con(il,i)会溢出integer的范围；
第四 ：后面那句“if max[i,j]=maxint then max[i,j]:=0;”是干什么，没道理吧，删掉了。。。
以下是我改过后并AC的程序 ：
{$R+,Q+,S+}
var
max:Array[1..300,1..30] of longint;
map:array[0..300] of longint;
i,j,n,k,il,l,all:longint;
function con(a,b:longint):longint;
begin
con:=0;
while a<b do
begin
inc(con,map[b]-map[a]);
inc(a);
dec(b);
end;
end;
begin
readln(n,k);
for i:=1 to n do
begin
read(map[i]);
max[i,1]:=con(1,i);
end;
for i:=2 to n do
for j:=2 to k do
begin
l:=0;
if j>i then break;
max[i,j]:=1000