PETROLM – spoj

Đề bài: http://vn.spoj.com/problems/PETROLM/

Thuật toán:

• Đây là một bài QHĐ cơ bản suy nghĩ một chút sẽ ra
• Các bạn hãy đọc code của mình sẽ hiểu ngay

Code:

uses math;
const
  fi='';//petrolm.inp';
  fo='';//petrolm.out';
  maxn=4000;
  oo=trunc(1e18);
type
  arr1 = array[1..maxn] of longint;
var
  tram,xe,csxe,cstram,kq : array[1..maxn] of longint;
  f : array[0..maxn,0..maxn] of int64;
  i,j,n,m : longint;
procedure enter;
  begin
    assign(input,fi);reset(input);
    readln(n);
    for i:=1 to n do read(xe[i]);
    read(m);
    for i:=1 to m do read(tram[i]);
    close(input);
  end;
procedure swap(var x,y : longint);
  var tg : longint;
  begin
    tg:=x;x:=y;y:=tg;
  end;
procedure qs(l,r : longint; var a,b : arr1);
  var i,j,x : longint;
  begin
    i:=l;j:=r;
    x:=a[(l+r) div 2];
    repeat
      while x>a[i] do inc(i);
      while xj;
    if il then qs(l,j,a,b);
  end;
procedure process;
  begin
    for i:=1 to n do csxe[i] := i;
    for i:=1 to m do cstram[i] := i;
    qs(1,n,xe,csxe);
    qs(1,m,tram,cstram);
    for i:=0 to n do
      for j:=0 to n do
        f[i,j] := oo;
    f[0,0] := 0;
    for i:=1 to n do f[i,i] := f[i-1,i-1] + abs(xe[i]-tram[i]);
    for j:=1 to m do
      for i:=j+1 to n do
        begin
          f[i,j] := min(f[i-1,j-1] + abs(xe[i]-tram[j]), f[i-1,j] + abs(xe[i]-tram[j]) );
          f[i,j] := f[i,j];
        end;
  end;
procedure print;
  begin
    assigN(output,fo);rewrite(output);
    writeln(f[n,m]);
    i:=n; j:= m;
    while (i>0) and (j>0) do
      begin
        if f[i,j]=f[i-1,j-1] + abs(xe[i]-tram[j]) then
          begin
            kq[csxe[i]] := cstram[j];
            dec(i);dec(j);
            continue;
          end;
        if f[i,j]=f[i-1,j] + abs(xe[i]-tram[j]) then
          begin
            kq[csxe[i]] := cstram[j];
            dec(i);
            continue;
          end;
      end;
    for i:=1 to n do write(kq[i],' ');
    close(output);
  end;
begin
  enter;
  process;
  print;
end.