问个题目 [复制链接]

【问题描述】
Frank是一个非常喜爱整洁的人。他有一大堆书和一个书架，想要把书放在书架上。书架可以放下所有的书，所以Frank首先将书按高度顺序排列在书架上。但是Frank发现，由于很多书的宽度不同，所以书看起来还是非常不整齐。于是他决定从中拿掉k本书，使得书架可以看起来整齐一点。
书架的不整齐度是这样定义的：每两本书宽度的差的绝对值的和。例如有4本书：
1x2
5x3
2x4
3x1
那么Frank将其排列整齐后是：
1x2
2x4
3x1
5x3
不整齐度就是2+3+2=7
已知每本书的高度都不一样，请你求出去掉k本书后的最小的不整齐度。
【输入数据】
第一行两个数字n和k，代表书有几本，从中去掉几本。(1<=n<=100, 1<=k<n)
下面的n行，每行两个数字表示一本书的高度和宽度，均小于200。
【输出数据】
一行一个整数，表示书架的最小不整齐度。
【样例】
book.in
4 1
1 2
2 4
3 1
5 3

book.out
3

江苏省夏令营（JSOI）考试末一题，用动态规划。
我参加的，我知道。

我用了贪心 不行。好像前面一个题目是贪心的

怎么动规能说下吗

DP!!!!!!!!

貌似有后效性

没有后效性的，经典DP。

你给多少悬赏

我有源程序

程序如下:

type
    at=record
            h:longint;
            r:longint;
            d:longint;
      end;
var
  a:array[0..201] of at;
  i,j,n,k,s,min:longint;
procedure sort(l,r:longint);
var
  i,j,x,y:longint;
begin
    i:=l;
    j:=r;
    x:=a[(l+r) div 2].h;
    repeat
          while a.h<x do i:=i+1;
          while x<a[j].h do j:=j-1;
          if not(i>j) then
          begin
                y:=a.h;
                a.h:=a[j].h;
                a[j].h:=y;
                i:=i+1;
                j:=j-1;
          end;
    until i>j;
    if l<j then sort(l,j);
    if i<r then sort(i,r);
end;
begin
    assign(input,'book.in');
    reset(input);
    assign(output,'book.out');
    rewrite(output);
    read(n,k);
    k:=n-k;
    fillchar(a,sizeof(a),0);
    for i:=1 to n do read(a.h,a.d);
    if (k=1)or(k=0) then begin writeln(0);close(input);close(output);halt;end;
    sort(1,n);
    for i:=0 to k do a.r:=i;
    min:=maxlongint;
    while a[0].r=0 do
    begin
          s:=0;
          for i:=1 to k-1 do
          begin
              s:=s+abs(a[a.r].d-a[a[i+1].r].d);
              if s>min then break;
          end;
          if s<min then min:=s;
          j:=k;
          while a[j].r=n-k+j do j:=j-1;
          a[j].r:=a[j].r+1;
          for i:=j+1 to k do a.r:=a[i-1].r+1;
    end;
    writeln(min);
    close(input);
    close(output);
end.
     

谁能告诉我01背包怎么想的啊？