Skip to content
Narrow screen resolution Wide screen resolution Auto adjust screen size Increase font size Decrease font size Default font size default color grey color
         
 | 
VNOI - Olympic tin học Việt Nam

Điểm tin VOJ

Số thành viên:6040
Số bài tập:1001
Số bài nộp:722923
Bài nộp hôm nay:0

Top 10 thành viên xuất sắc

HạngThành viênĐiểm
1mr_invincible587.9
2white_cobra418.6
3hieult403.4
4phaleq384.0
5vodanh9x368.2
6con_nha_ngheo352.0
7flash_mt350.2
8darksabers349.8
9yenthanh132345.3
10rockman9x_94343.1
[VOJ] Mã nguồn #206 - LAZYCOWS - QHĐ O(n.k)
Ngày: 23-03-2011
Cập nhật: 17-04-2011
Người gửi: yenthanh132
Ngôn ngữ: Pascal
Xem: 759

Điểm: 4.7/5 (10 Phiếu)


Program LAZYCOWS;
Const MaxN=1000;
      MaxC=100000000;
Type Cow=Record y:Longint; x:Byte End;
Var a:array[1..MaxN] of Cow;
    l:array[1..MaxN,1..MaxN,0..2] of Longint;
    p:array[1..MaxN] of Byte;
    n,k,test,t:Integer;
    f:Text;
    kq:Longint;
Procedure Input;
Var i:Integer;
Begin
  Readln(f,n,k);
  For i:=1 to n do Readln(f,a[i].x,a[i].y);
End;
Procedure Swap(var a,b:cow);
Var t:cow;
Begin
  t:=a; a:=b; b:=t;
End;
Function Min(a,b:Longint):Longint;
Begin
  If a<b then Exit(a) else Exit(b);
End;
Procedure QuickSort(l,r:Integer);
Var i,j:Integer;
    k:Cow;
Begin
  If l>=r then exit;
  i:=l; j:=r;
  k:=a[random(r-l+1)+l];
  Repeat
    While (a[i].y<k.y) or ((a[i].y=k.y) and (a[i].x<k.x)) do Inc(i);
    While (a[j].y>k.y) or ((a[j].y=k.y) and (a[j].x>k.x)) do Dec(j);
    If i<=j then
      Begin
        If i<j then Swap(a[i],a[j]);
        Inc(i); Dec(j)
      End;
  Until i>j;
  QuickSort(l,j); QuickSort(i,r);
End;
Procedure Optimize;
Var i,j,p,h:Integer;
    v:Longint;
Begin
  FillChar(l,sizeof(l),0);
  l[1,1,0]:=1; l[1,1,1]:=2;
  l[1,1,2]:=MaxC; l[1,2,2]:=2;
  For i:=2 to n do
    For j:=1 to k do
      For p:=0 to 2 do
        Begin
          v:=maxC;
          Case p of
          0:Begin
              If j>1 then
                For h:=0 to 2 do v:=Min(v,l[i-1,j-1,h]+1);
              If i>j then
                If a[i].x=a[i-1].x then v:=Min(v,l[i-1,j,0]+a[i].y-a[i-1].y)
                else v:=Min(v,l[i-1,j,2]+a[i].y-a[i-1].y);
            End;
          1:Begin
              If j>1 then
                For h:=0 to 2 do v:=Min(v,l[i-1,j-1,h]+2);
              If i>j then
                v:=Min(v,l[i-1,j,1]+(a[i].y-a[i-1].y)*2)
            End;
          2:Begin
              If j>2 then
                For h:=0 to 2 do v:=Min(v,l[i-1,j-2,h]+2);
              If j>1 then
                v:=Min(v,l[i-1,j-1,0]+a[i].y-a[i-1].y+1);
              If i>j then
                v:=Min(v,l[i-1,j,2]+(a[i].y-a[i-1].y)*2);
             End;
          End;
          l[i,j,p]:=v;
        End;
  kq:=l[n,k,0];
  For p:=1 to 2 do kq:=Min(kq,l[n,k,p]);
End;
 
BEGIN
  Assign(f,'TEST.TXT'); Reset(f);
  Readln(f,test);
  For t:=1 to test do
    Begin
      Input;
      QuickSort(1,n);
      Optimize;
      Writeln(kq);
    End;
  Close(f);
END.