tailieunhanh - Sáng tạo trong kỹ thuật và lập trình

Tài liệu dành cho giáo viên, sinh viên chuyên ngành công nghệ thông tin - Sáng tạo trong kỹ thuật và lập trình | 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 .