Ô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.
Nội dung trích xuất từ tài liệu:
Ô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ấtThi HSG Quốc gia 2010CCKLK: Dãy con chung không liền kề dài nhấtCho dãy số nguyên dương x = (x1, x2, ..., xn). Dãy y = (xi1, xi2, ..., xik) được gọi là dãy con không liền kề củadã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.CCKLK.INP CCKLK.OUT Giải thích5 6 2 CCKLK.INP: Dòng đầu: n m. Từ dòng thứ hai trở đi: Dãy số a,1 5 3 8 2 tiếp đến là dãy số b.2 1 3 4 2 6 CCKLK.OUT: k.Thuật toánQuy hoạch động.Gọi d(i,j) là đáp số của bài toán khi xét hai dãy a[1..i] và b[1..j]. 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ạpO(n.m)Chương trình Pascal (* CCKLK.PAS k: chieu dai day con chung khong lien ke dai nhat cua hai day so nguyen duong a[1..n], b[1..m] *) const fn = ccklk.inp; gn = ccklk.out; bl = #32; nl = #13#10; mn = 1001; type int = integer; mi1 = array[0..mn] 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[1..i], b[1..j] 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[1..3] 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 begin if (a[1] = b[j]) then v := 1; c[y][j] := v; end; v := 0; for i := 2 to n do begin c[z][0] := 0; if (a[i] = b[1]) then v := 1; c[z][1] := v; for j := 2 to m do if (a[i] = b[j]) then c[z][j] := c[x][j-2]+1 else c[z][j] := Max(c[z][j-1],c[y][j]); t := x; x := y; y := z; z := t; end; QHD := c[y][m];end;BEGIN Doc; Ghi(QHD); write(nl, Fini ); readln; END.Chương trình CPP /* DevC++ CCKLK.CPP k: chieu dai day con chung khong lien ke dai nhat cua hai day so nguyen duong a[1..n], b[1..m] */ #include #include using namespace std; // D A T A A N D V A R I A B L E const char * fn = ccklk.inp; const char * gn = ccklk.out; const int mn = 1001; int n, m; int a[mn],b[mn]; // P R O T O T Y P E S void Doc(); int QHD(); // Quy hoach dong void Ghi(int); int Max(int,int); // I M P L E M E N T A T I O N int main() { Doc(); Ghi(QHD()); cout > n >> m; cout = 0, if i < 1 || j < 1 */ int QHD() { int *x, *y, *z, *t; int i, j , m1 = m+1, v ; x = new int[m1]; y = new int[m1]; z = new int[m1]; // Init i = 0 memset(x,0,sizeof(int)*m1); // Init i = 1 y[0] = 0; v = 0; for (j = 1; j #include #include //#include using namespace std;// D A T A A N D V A R I A B L E Schar * fn = ondinh.inp;char * gn = ondinh.out;const int mn = 10001;const int mm = 50001;typedef struct { int a, b; } cung;cung c[mm];int len[mn]; // len[i] chieu dai s => ichar mark[mn]; // mark[i] danh dau dinh i: // Chua xet 0; Co trong hang doi q 1; Da xu li 2int d[mn]; // d[i] so luong duong ngan nhat s => iint q[mn]; // hang doiint n, m, s ; // so d ...