tailieunhanh - Ôn tập thi học sinh giỏi quốc gia môn Toán - Tin 2010: Dãy con chung không liền kề dài nhất

Hãy tham khảo tài liệu ôn tập thi học sinh giỏi môn Toán - Tin năm 2010: Dãy con chung không liền kề dài nhất sẽ giúp các bạn học sinh có thêm tư liệu chuẩn bị ôn luyện và bổ trợ kiến thức cho kỳ thi sắp tới cũng như bổ trợ kiến thức cho giáo viên ra đề thi. Mời các bạn học sinh và quý thầy cô giáo cùng tham khảo. | Thi HSG Quốc gia 2010 CCKLK Dãy con chung không liền kề dài nhất Cho dãy số nguyên dương x x1 x2 . xn . Dãyy xi1 xi2 . xik được gọi là dãy con không liền kề của dãy x nếu 1 i1 i2-1 . ik-1 n. Cho 2 dãy số nguyên a gồm n phần tử và b gồm m phần tử. Xác định chiều dài k của dãy con chung không liền kề dài nhất của a và b. 2 m n 1000 1 ai bi 10000. 5 6 1 5 3 8 2 2 1 3 4 2 6 2 Giải thích Dòng đầu n m. Từ dòng thứ hai trở đi Dãy số a tiếp đến là dãy số b. k. Thuật toán Quy hoạch động. Gọi d i j là đáp số của bài toán khi xét hai dãy a và b . Ta có Nếu i 0 thì ta quy ước d i j 0 Nếu a i b j thì d i j d i-2 j-2 Nếu a i b j thì d i j max d i-1 j d i j-1 . Để cài đặt ta dùng 3 mảng một chiều x y và z với ý nghĩa x j d i-2 j y j d i-1 j và z j d i j . Khi đó hệ thức trên được viết là Nếu i 0 thì ta quy ước d i j 0 Nếu a i b j thì d i j d i-2 j-2 ứng với z j x j-2 Nếu a i b j thì d i j max d i-1 j d i j-1 ứng với z j max y j z j-1 . Muốn tránh các phép copy dữ liệu từ y sang x từ z sang y và từ x sang z ta chỉ cần tráo đổi các con trỏ mảng. Độ phức tạp O Chương trình Pascal k chieu dai day con chung khong lien ke dai nhat cua hai day so nguyen duong a b const fn gn bl 32 nl 13 10 mn 1001 type int integer mi1 array of int var n m int a b mi1 function Max a b int int begin if a b then Max a else Max b end procedure Doc var i int f text begin assign f fn reset f read f n m writeln n bl m for i 1 to n do read f a i for i 1 to m do read f b i write nl a for i 1 to n do write a i bl write nl b for i 1 to n do write b i bl close f end procedure Ghi k int var g text begin assign g gn rewrite g writeln g k close g end d i j dap so cua bai toan voi a b d i j d i-2 j-2 1 if a i b j Max begin d i j-1 d i-1 j end elsewhere 0 if i 1 j 1 function QHD int var i j v int c array of mi1 x y z t int begin x 1 y 2 z 3 Init i 0 fillchar c x sizeof c x 0 Init i 1 c y 0 0 v 0 for j 1 to m do .