//
you're reading...
Chủ đề quy hoạch động, Lập trình Pascal nâng cao, Đề thi Tin học quốc tế IOI

Chuyên đề Quy hoạch động – Palindrome

[Nguồn] []


Đề bài


( Đề thi Quốc Tế năm 2000 )

Palindrome là một xâu đối xứng tức là một xâu mà đọc từ trái sang phải cũng như đọc từ phải sang trái . Bạn cần viết một chơng trình với một xâu cho trớc , xác định số ít nhất các kí tự cần chèn vào xâu để nhận được một palindrome  .

Ví dụ : Bằng cách chèn 2 kí tự vào xâu ‘ Ab3d ‘ ta nhận được một palindrome . Tuy nhiên nếu chèn its hơn 2 kí tự thì không thể tạo được một palindrome .

Dữ liệu: Vào file input : PALIN .IN  

  • Dòng thứ nhất gồm một số nguyên là độ dài N của xâu , 3<=N<=5000.
  • Dòng thứ hai gồm một xâu có độ dài N. xâu gồm các kí tự là các chữ cái hoa A..Z, các chữ cái thường : a.. z và các chữ số thập phân .9 ,các chữ cái hoa và thường xem như khác nhau .

Dữ liệu :   Ra file output : PALIN.OUT 

  • Dòng một là số lượng các kí tự cần chèn vào.

Ví dụ:    

   PALIN.IN                                                                                        PALIN.OUT

5 Ab3bd                                                                                              2

a


Hướng dẫn


Gọi xâu dữ liệu vào là s . Ta sẽ tìm chiều dài của dãy con đối xứng cực đại trích từ s là s1 . Khi đó số ký tự cần thêm sẽ là =Length(s)-Length(s1) .Dãy con ở đây đợc hiểu là dãy thu đợc từ s bằng cách xoá đi một số phần tử trong s .

Gọi Maxd[i,j] là chiều dài của dãy con dài nhất thu đợc từ đoạn s[i..j] . Ta sẽ có :

Nếu S[i]=S[j] thì Maxd[i,j]=Maxd[i+1,j-1]+2 ;

Nếu       S[i]<>S[j] thì Maxd[i,j]:=Max Maxd[i,j-1] , Maxd[i+1,j]

Tức là chúng ta cần tính Maxd[1,n]. Nhn với dữ liệu N<=5000 thì điều này trở thành hoang tởng .  Ta có thể nhìn nhận rõ hơn thì thấy rằng chúng ta có thể hoàn toàn tiết kiệm đợc rất nhiều bộ nhớ :

Gọi Luu[0..N+1] là mảng cập nhật các bớc thực hiện . Tại bớc cập nhật thứ j ta có Luu[j]:=Maxd[i,j].

Ta sẽ có lại bảng truy hồi nh sau :

Nếu S[i]=S[j] thì Luu[i]:=Luu[i+1] cũ + 2

Nếu S[i]<>S[j] thì Luu[i]:=Max Luu[i] cũ , Luu[i+1] cũ

Ta tính từ dới lên , tức là tính Luu[i] với i:=n ..1 thì D[i+1] cũ sẽ bị ghi đè . Và lúc đó dùng tg để lu lại .

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

 

procedure qhd;

begin

for j:=1 to n do

begin

luu[j]:=1;    tg:=0;

for i:=j-1 downto 1 do

begin

t:=luu[i];

if s[i]=s[j] then luu[i]:=tg+2 else

Luu[i]:=max(Luu[i],Luu[i+1]);

tg:=t;

end;

end;

end;

Như vậy số ký tự cần thêm vào :  N-Luu[1].


Lời giải – Chương trình


b

b


Tài liệu tham khảo


  1. a
  2. a

About pascalteacher

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

Thảo luận

Chưa có phản hồi.

Gửi phản hồ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ả

Tháng Mười Một 2016
M T W T F S S
« Oct   Dec »
 123456
78910111213
14151617181920
21222324252627
282930  

NCT Computer

Flickr Photos

A bellezza di a natura (C☺rsica)

Southern White-faced Owl D75_5752.jpg

2016 Lake Yamanaka winter Fuji

More Photos

Thống kê

  • 78,768 lượt xem

%d bloggers like this: