Các bài toán sử dụng quy hoạch động, cấu trúc dữ liệu và đồ thị LTTK Education xin giới thiệu với bạn đọc Các bài toán sử dụng quy hoạch động, cấu trúc dữ liệu và đồ thị để bạn đọc tham khảo học tập những điều bổ ích mà tài liệu này mang lại nhé! Chúc các em học tập thật tốt và mang lại nhiều kết quả khả quan cho bản thân nhé! ✪ ✪ ✪ ✪ ✪ Link tải tài liệu: LINK TẢI TÀI LIỆU Spoiler: Read me Mục lục Phần 1: Quy hoạch động ............................................................................................................ 2 I. Dãy con đơn điệu của dãy số và ứng dụng. ..................................................................... 2 II. Quy hoạch động cấu hình. ............................................................................................... 6 III. Đệ quy có nhớ. ........................................................................................................... 17 IV. Quy hoạch động trạng thái. ........................................................................................ 21 V. Quy hoạch động trên cây ............................................................................................... 23 VI. Quy hoạch động với nhân ma trận .............................................................................. 26 VII. Một số bài toán quy hoạch động khác ........................................................................ 27 Phần 2: Cấu trúc dữ liệu. .......................................................................................................... 35 I. Ngăn xếp và Hàng đợi. .................................................................................................. 35 II. Hàng đợi ưu tiên. ........................................................................................................... 38 Phần 3: Đồ thị........................................................................................................................... 41 I. Depth-First Search (DFS). ............................................................................................. 41 II. Breadth-First Search (BFS)............................................................................................ 42 III. Cầu và khớp. .............................................................................................................. 45 IV. Thành phần liên thông mạnh và Song liên thông. ....................................................... 46 V. Chu trình. ....................................................................................................................... 47 VI. Chu trình Euler. .......................................................................................................... 48 VII. Sắp xếp Topo. ............................................................................................................ 50 VIII. Cây khung nhỏ nhất. .................................................................................................. 51 IX. Đường đi ngắn nhất. ................................................................................................... 54 Phần 1: Quy hoạch động (qhđ) I. Dãy con đơn điệu của dãy số và ứng dụng. 1. Dãy con đơn điệu tăng dài nhất: Bản dễ : http://vn.spoj.com/problems/LIQ Bản khó : http://vn.spoj.com/problems/LIS Cách 1: +Mảng qhđ F với i = (1 n):độ dài dãy con tăng dài nhất có phần tử cuối cùng là phần tử thứ i. +Cơ sở qhđ F[0] = 0 với a[0] = –oo; +Công thức qhđ F = max(F[j] + 1) với j = (0 i – 1) và a[j] > a; +Kết quả: res = max(F) với i = (1 n); +ĐPT: O(n2). Cách 2: +Mảng qhđ h với i = (1 res): -F[h] = i; -a[h] nhỏ nhất có thể. Ví dụ: n = 5; a: 2 1 3 4 1 F: 1 1 2 3 1 mảng h sau khi tính xong: 5 3 4 +Cơ sở qhđ h[1] = 1; res = 1; +Xét i chạy từ 2 n ta có: - Mảng h đã được xây dựng cho dãy số từ 0 i – 1; - Để tính F ta phải tìm 1 chỉ số j từ 1 i – 1 sao cho a > a[j] và F[j] lớn nhất, do tính chất của dãy h nên ta sẽ chặt nhị phân trên dãy h để tìm 1 chỉ số d sao cho a[h[d]] < a ≤ a[h[d + 1]]; Lúc đó F = d + 1; Mô tả thuật toán: h[1] := 1; res := 1; for i := 2 to n do begin d := 0; c := res + 1; while d + 1 <> c do begin m := (d + c) div 2; if a <= a[H[m]] then c := m else d := m; end; h[d + 1] := i; if d = res then inc(res); end; NOTE: Câu lệnh : if a <= a[H[m]] then c := m else d := m; dấu <= sẽ tùy trường hợp và thay đổi, cụ thể: tìm dãy con tăng: <= tìm dãy con giảm: >= tìm dãy con ko giảm: < tìm dãy con ko tăng: > <dễ dàng cm đc> 2. Sequences: http://vn.spoj.com/problems/SPSEQ +Mảng qhđ: - T độ dãy con tăng dài nhất từ 1 i nhận a làm phần tử cuối cùng - S độ dãy con tăng dài nhất từ n i nhận a làm phần tử cuối cùng - 2 mảng trên tính bằng bài LIS +Kết quả : res = max{2 * min(F, S) – 1} với i = 1 n 3. Chia dãy [URL][URL][URL][URL]http://vn.spoj.com/problems/QBDIVSEQ[/URL][/URL][/URL][/URL] +Kết quả bài toán: res = độ dài dãy con giảm dài nhất +Chứng minh: - Không có cách chia với số nhóm < res: Giả sử dãy con giảm dài nhất là a[i.1];a[i.2]...a[i.res]. Do số nhóm < res nên theo nguyên lí dirichle phải có ít 2 số trong res số trên thuộc cùng 1 nhóm. Giả sử 2 số đó là a[i.h] và a[i.k] với i.h < i.k. Do 2 số trên thuộc 1 nhóm nên a[i.h] ≤ a[i.k];mặt khác 2 số trên thuộc dãy giảm dần nên a[i.h] > a[i.k] Vô lý - Tồn tại cách chia với số nhóm = res: Gọi F[i] là độ dài dãy con giảm dài nhất từ 1 i với a[i] là phần tử cuối cùng (1 ≤ F[i] ≤ res). Tất cả những phần tử có cùng giá trị F[i] sẽ cùng thuộc 1 nhóm có res nhóm với mỗi nhóm đều lập thành 1 dãy ko giảm (dễ dàng chứng minh được). NOTE: Các trường hợp chia nhóm sao cho các phần tử trong nhóm lập thành: (sẽ có kết quả tương ứng là:) - dãy tăng: độ dài dãy con không tăng dài nhất - dãy giảm: độ dài dãy con ko giảm dài nhất - dãy ko giảm: độ dài dãy con giảm dài nhất - dãy ko tăng: độ dài dãy con tăng dài nhất[/I][/I][/I][/I]
