【算法分析】
以f[5,2]为例：
若取走第５个数，则f[5,2]=f[4,1]
若不取走第５个数，且不取走第４个数，则f[5,2]=f[4,2]+abs(b[5]-b[4]]
若不取走第５个数，取走第４个数，不取走第３个数，则f[5,2]=f[3,1]+abs(b[5]-b[3])
若不取走第５个数，取走第４个数，取走第３个数，则f[5,2]=f[2,0]+abs(b[5]-b[2])
由此可见，若不考虑取走第n个数的话，
f[i,j]=min{f[i-p-1,j-p]+abs(b-b[i-p-1])}
(j≤i≤n,0≤p≤j≤min{i-1,k})
当然，当i-p-1=0时，abs(b-b[i-p-1]=0，边界条件是f[0,0]=0。
最后，用打擂台的方式将未考虑的情况和求出的f[i,j]中选取最小的作为问题的解。
【程序清单】
var
n,k,i,j,p,t:longint;
a,b:array[1..100] of longint;
f:array[0..101,0..101] of longint;
procedure qsort(l,r:longint);
var
i,j,x,t:longint;
begin
i:=l;j:=r;x:=a[(l+r) div 2];
repeat
while a<x do inc(i);
while x<a[j] do dec(j);
if i<=j then
begin
t:=a;a:=a[j];a[j]:=t;
t:=b;b:=b[j];b[j]:=t;
inc(i);dec(j);
end;
until i>j;
if l<j then qsort(l,j);
if i<r then qsort(i,r);
end;
begin
assign(input,'book.in');reset(input);
assign(output,'book.out');rewrite(output);
read(n,k);
for i:=1 to n do read(a,b);
qsort(1,n);
f[0,0]:=0;
for i:=1 to n do
for j:=0 to k do
begin
if j>=i then break;
f[i,j]:=maxlongint;
for p:=0 to j do
begin
t:=f[i-p-1,j-p];
if i-p-1>0 then inc(t,abs(b-b[i-p-1]));
if f[i,j]>t then f[i,j]:=t;
end;
end;
for i:=1 to k do
if f[n,k]>f[n-i,k-i] then f[n,k]:=f[n-i,k-i];
writeln(f[n,k]);
close(input);close(output);
end.
【考察知识点】
动态规划的应用。
