//
you're reading...
Chủ đề quy hoạch động, Dùng cho cấp THPT, Dùng cho thi học sinh giỏi

Chuyên đề: Quy hoạch động – Bài tập 02: Bài toán nối điểm (Wires)

Đề bài:


Trên hai đuờng thẳng song song L1 và L2 người ta đánh dấu trên mỗi đường N điểm. Các điểm trên đừơng thẳng L1 được đánh số từ 1 đến N, từ trái qua phải, còn các điểm trên đường thẳng L2 được đánh số bởi P[1],P[2],…P[N] cũng từ trái qua phải, trong đó P[1],P[2],..P[N] là một hoán vị của các số 1,2,…N.

Ta gọi các số gán cho các điểm là số hiệu của chúng . Cho phép nối hai điểm trên 2 đường thẳng có cùng số hiệu .

Yêu cầu : Tìm cách nối được nhiều cặp điểm nhất với điều kiện các đoạn nối không được cắt nhau .

Dữ Liệu : Vào từ File BaiToan2.Inp:

  • Dòng Đầu tiên chứa số nguyên dương N (N<=1000).
  • Dòng thứ hai chứa các số P[1],P[2],….P[N].

Kết quả ghi ra file : BaiToan2.Out:

  • Dòng đầu tiên chứa K là số lượng đoạn nối tìm được
  • Dòng tiếp theo chứa K số hiệu của các đầu mút của các đoạn nối được ghi theo thứ tự tăng dần .

Ví dụ


      WIRES.INP         WIRES.OUT
9

2 5 3 8 7 4 6 9 1

5 2 3 4 6 9

Hướng dẫn


Gọi Maxd[I] là số đoạn thẳng tối đa của các cặp nối của các điểm từ 1I .  Chúng ta sẽ có công thức quy hoạch động như sau :

Maxd[I]:=MaxMaxd[P[J]]+1;J:= ViTri(I)

Trong đó ViTri (I) Là hàm cho biết Vị trí Của I Trong Dãy P[1],P[2],..P[N] (Tức là I = P[X] Thì ViTri(I) = X);

Bằng cách phân tích hoàn toàn tơng tự như bài toán 1 mà ta có công thức truy hồi như trên . Các bước giải bài toán có thể được nói gọn trong hai thủ tục và hàm :

Funtion ViTri(I:Integer):Integer;
Var       J:Integer;
Begin
     For J:=1 To N Do
     If P[J]=I Then
     Begin
          ViTri:=J;
          Exit;
      End;
End;

Thủ  Tục quy hoạch động như sau :

Procedure Quy_Hoach_Dong;
Begin
      Maxd[0]:=0;
      For I:=1 To N Do
      Begin
          Max:=0;
          For J:=0 To ViTri(I) Do
              If Maxd[P[J]]>Max Then
                 Begin
                     Luu[I]:=J;
                     Max:=Maxd[P[J]];
                 End;
          Maxd[I]:=Max;
     End;
End;

Mảng Luu là mảng Luu[I] lưu lại điểm trước I mà tiếp đó sẽ nối I . Chính vì điều đó chúng ta có thể ghi ra ngược lại một cách dễ dàng.


Bài giải


Program B02;
Uses Crt;
Const
Fi=’WIRES.inp’;}
Fo=’WIRES.out’;
Var
A, MaxD, Luu:Array[1..1000]Of Integer;
Ok: Array[1..1000]Of Boolean;
Luu_Gia_Tri,Gia_Tri_Max,N,i,j:Integer;
F:Text;
Procedure Readfile;
Begin

Assign(f,Fi);
Reset(f);
Readln(f,n);
For i:=1 To n Do
Read(f,A[i]);
Close(f);

End;

Function Vitri(i:Integer):Integer;
Var j:Integer;
Begin
For j:=1 To N Do
If A[j]=i Then
Begin
Vitri:=j;
Exit;
End;
End;

Procedure Init;
Begin
Fillchar(MaxD,Sizeof(MaxD),0);
Luu:=MaxD;
Fillchar(Ok,Sizeof(Ok),True);
Gia_Tri_Max:=0;
End;

Procedure Xuli;
Var Max:Integer;
Begin
For i:=1 To n Do
Begin
Max:=0;
For j:=1 To Vitri(i) Do
If Max<MaxD[A[j]] Then
Begin
Max:=MaxD[A[j]];
Luu[i]:=A[j];
End;
MaxD[i]:=Max+1;
End;
For i:=1 To n Do
If Gia_Tri_Max<MaxD[i] Then
Begin
Gia_Tri_Max:=MaxD[i];
Luu_Gia_Tri:=i;
End;
Ok[Luu_Gia_Tri]:=False;
J:=Luu[Luu_Gia_tri];
While j<>0 Do
Begin
Ok[j]:=false;
i:=j;
j:=Luu[i];
End;
End;

Procedure Writefile;
Begin
Assign(f,Fo);
Rewrite(f);
Writeln(f,Gia_Tri_Max);
For i:=1 To n Do
If Not Ok[i] Then
Write(f,i,’ ‘);
Close(f);
End;

Begin
Init;
Readfile;
Xuli;
Writefile;
End.

 

Advertisements

About pascalteacher

Trang thông tin Toán học và Tin học

Thảo luận

Không có bình luận

Trả lời

Mời bạn điền thông tin vào ô dưới đây hoặc kích vào một biểu tượng để đăng nhập:

WordPress.com Logo

Bạn đang bình luận bằng tài khoản WordPress.com Log Out / Thay đổi )

Twitter picture

Bạn đang bình luận bằng tài khoản Twitter Log Out / Thay đổi )

Facebook photo

Bạn đang bình luận bằng tài khoản Facebook Log Out / Thay đổi )

Google+ photo

Bạn đang bình luận bằng tài khoản Google+ Log Out / Thay đổi )

Connecting to %s

Các tác giả

Chuyên mục

Tháng Mười 2016
H B T N S B C
« Th9   Th11 »
 12
3456789
10111213141516
17181920212223
24252627282930
31  

NCT Computer

Flickr Photos

lost

Lookkk deeeply into my eyes....

Cimitero San Michele

More Photos

Thống kê

  • 115,518 lượt xem

pascalteacher.nct@gmail.com


Trang huấn luyện học sinh giỏi Tin học

%d bloggers like this: