Tài liệu XÂY DỰNG CÔNG THỨC QUY HOẠCH ĐỘNG BẰNG PHƯƠNG PHÁP PHÂN TÍCH ĐƠN VỊ DỮ LIỆU CUỐI

XÂY DỰNG CÔNG THỨC QUY HOẠCH ĐỘNG BẰNG PHƯƠNG PHÁP PHÂN TÍCH ĐƠN VỊ DỮ LIỆU CUỐI THPT chuyên LƯƠNG VĂN TỤY 1. Khái niệm đơn vị dữ liệu cuối. Trong một lớp rất lớn các bài toán Tin học, chúng ta phải đếm các cấu hình tổ hợp có thứ tự (x1, x2,...,xn) thỏa mãn một tính chất đặc trưng nào đó hoặc tìm giá trị tối ưu (theo một nghĩa nào đó) của các cấu hình này. Chúng ta sử dụng phương pháp quy hoạch động theo cách sau đây: Tìm lời giải từng bước một: bước thứ k, đếm các cấu hình (x 1, x2,...,xk) hay tìm giá trị tối ưu của các loại cấu hình k phần tử (x1, x2,...,xk). Việc tìm lời giải từng bước một này thể hiện nguyên lý “chia để trị” trong tin học: Thay vì trực tiếp tìm lời giải bài toán lớn, ta giải quyết các bài toán nhỏ cùng mô hình, sau đó dựa trên kết quả các bài toán nhỏ để tìm kết quả bài toán lớn. Nói một cách nôm na, nó giống như việc chúng ta xây một bức tường thì phải xây từ móng, sau đó xây lần lượt các hàng gạch cho đến khi có một bức tường hoàn chỉnh, hàng gạch thứ k (tính từ móng trở lên) chính là hình ảnh trực quan của đơn vị dữ liệu cuối ở bước thứ k. Đối với cấu hình ta xây dựng đến bước thứ k: (x 1, x2,...,xk) thì ta nói xk là đơn vị dữ liệu cuối ở bước này. Việc xác định giá trị của xk không hề khó khăn vì trước đó đã xây dựng được (x1, x2,...,xk-1), từ đó có được phương án tính số lượng hay giá trị tối ưu cho bước thứ k. Một điểm mấu chốt khi phân tích quy nạp xây dựng bước thứ k đó là: Nếu ta coi mỗi phần tử của cấu hình đang xây dựng như là một vị trí trên đường đi thì để đến được vị trí thứ k ta phải qua vị trí thứ k-1. Nói cách khác, để đến được vị trí cuối x k đã xác định thì xk-1 phải là một trong các vị trí có thể “đi đến x k”. Từ nhận xét mấu chốt này mà việc phân tích cấu trúc x k – đơn vị dữ liệu cuối bước k – để tìm ra những vị trí có thể của xk-1 chính là yếu tố quyết định để có được lời giải cho bài toán. 2. Cơ sở toán học: A/ Phương pháp quy nạp: “Nếu một mệnh đề toán học P(n) phụ thuộc biến số tự nhiên n là đúng với giá trị cơ sở n = a, ngoài ra khi P(k) đúng kéo theo P(k+1) đúng thì mệnh đề P(n) đúng với mọi số tự nhiên n không nhỏ hơn a”. Điều quan trọng nhất được áp dụng ở đây không phải dùng phương pháp quy nạp chứng minh bài toán mà chính là cách chứng minh P(k+1) đúng – để làm điều này, trong phương pháp quy nạp người ta đã vận dụng thật sáng tạo cơ sở đã có đó là 1 P(n) đúng với các n không quá k. Việc này hoàn toàn tương tự khi chúng ta phân tích xây dựng xk theo các giá trị đã có trước đó trong cấu hình đang xây dựng của bài toán. B/ Công thức truy hồi: Có hai dạng công thức truy hồi chúng ta sẽ sử dụng: 1/ Một dãy số hoàn toàn xác định khi biết k giá trị đầu tiên và công thức xác định một số hạng theo k số hạng liền trước nó: {Fn} xác định nếu biết F1, F2,...,Fk và công thức Fn = F(Fn-1,Fn-2,...,Fn-k). 2/ Một dãy số hoàn toàn xác định khi biết giá trị đầu tiên và công thức xác định một số hạng theo các số hạng trước nó: {Fn} xác định nếu biết F1 và công thức Fn = F(Fn-1,Fn-2,...,F1). Việc tính các giá trị ban đầu F1, F2, ..., Fk gọi là bước cơ sở, việc tìm công thức cho phép tính một số hạng của dãy theo các số hạng trước nó gọi là bước quy nạp. 3. Các bài toán áp dụng: Sau đây xin được nêu 20 bài toán để thấy được những vận dụng phong phú của việc phân tích đơn vị dữ liệu cuối. Các bài toán được chọn đều là đề thi trong các kỳ thi học sinh giỏi khu vực, Quốc gia và đề thi của nhiều nước trên thế giới. Bài Toán 1: Đếm xâu nhị phân. Đề bài: Cho số nguyên dương n. Tính số xâu nhị phân độ dài n không có 2 chữ số 1 liền nhau. Xây dựng giải thuật: Ta có thể liệt kê mọi xâu độ dài n không có 2 chữ số 1 liền nhau để đếm. Tuy nhiên phương án này rõ ràng không khả thi, sẽ không có đủ bộ nhớ và nhất là không có thời gian để làm công việc này khi n khá lớn vì lúc đó số lượng xâu cần liệt kê nhiều đến mức “kinh khủng”. Từ nhận xét: Một xâu độ dài n thỏa mãn yêu cầu bài toán (không có 2 ký tự 1 liên tiếp) thì xâu con n-1 ký tự đầu tiên của nó cũng thỏa mãn điều này, thế có nghĩa là để có xâu độ dài n ta chỉ việc thêm 0 hoặc 1 vào sau xâu độ dài n-1 như vậy mỗi đơn vị dữ liệu là một ký tự và đơn vị dữ liệu cuối ở bước thứ k là ký tự thứ k của xâu. Từ đó bằng phương pháp phân tích quy nạp, ta có thể xây dựng công thức quy hoạch động cho phép tính số xâu độ dài n theo số xâu có độ dài nhỏ hơn cùng thỏa mãn yêu cầu bài toán. Gọi F[k] là số xâu nhị phân độ dài k không có 2 chữ số 1 liền nhau. Bước cơ sở: n = 1: có 2 xâu thoả mãn là ‘0’ và ‘1’ nên F[1]:=2. n = 2: có 3 xâu thoả mãn là ‘00’;’01’và ‘10’ nên F[2]:=3. 2 Bước quy nạp: Giả sử đã tìm được các F[i] với i:=1,2…,k-1. Ta tính F[k] – số xâu độ dài k thỏa mãn bài toán có được do: + Thêm 0 vào sau 1 xâu độ dài k – 1, số xâu loại này bằng số xâu độ dài k-1 không có 2 chữ số 1 liền nhau và bằng F[k-1]. + Thêm 1 vào sau 1 xâu độ dài k – 1, để tạo xâu độ dài k thoả mãn yêu cầu thì ký tự cuối cùng xâu độ dài k-1 phải là 0, do đó số xâu loại này bằng số xâu độ dài k-2 không có 2 chữ số 1 liền nhau và bằng F[k-2]. Vậy F[k] = F[k – 1] + F[k – 2] (1) Do đã biết F[1], F[2] nên từ công thức này ta có thể tính F[n] với n tùy ý. Chú ý khi viết chương trình: + F[n] rất lớn (cỡ hàng nghìn chữ số) khi n khá lớn, vì vậy ta phải xây dựng và thực hiện tính toán trên các số nguyên lớn. Bài này chỉ cần xây dựng phép toán cộng số lớn (dùng xâu hoặc mảng 1 chiều) + Từ công thức (1) ta thấy rằng để tính F[k] chỉ cần 2 số hạng ngay trước nó nên không cần lưu lại cả mảng F làm gì cho tốn bộ nhớ. Ta sẽ dùng ba biến F1, F2, F3 và luân phiên tính F3 theo F1, F2 sau đó cập nhật lại F1=F2, F2=F3 trong vòng lặp đến khi tính được F[n]. Bài Toán 2 (Mở rộng): Tương tự như trên, ta xây dựng công thức tính số xâu nhị phân độ dài n không có k chữ số 1 liền nhau (k>=2). Ở đây ta cũng gọi F[n] để giữ giá trị số xâu nhị phân không có k chữ số 1 liền nhau và có độ dài n. Bước cơ sở: Ta thấy F[0]:=1; F[i]:=2i với i:=1,2,..k-1. Với i:=k, F[k] = 2k – 1 (trừ xâu có k chữ số 1) Bước quy nạp: + Thêm 0 vào sau 1 xâu độ dài n – 1, số xâu loại này bằng số xâu độ dài n-1 không có 2 chữ số 1 liền nhau và bằng F[n-1]. + Thêm 1 vào sau 1 xâu độ dài n – 1 cũng tạo thành F[n-1] xâu nhị phân mới có độ dài n nhưng trong đó có một số xâu không thoả mãn vì k chữ số liên tiếp cuối cùng bằng 1. Số xâu sau khi thêm 1 có k chữ số cuối bằng 1 bằng số xâu độ dài n-1 thỏa mãn bài toán và có k-1 chữ số cuối cùng là 1 : x 1x2..xn-k-1xn-k11…1, khi đó xn-k = 0 và vì vậy số xâu loại này bằng số xâu x1x2..xn-k-1 thỏa mãn bài toán và bằng F[n-k-1], từ đó số xâu độ dài n tận cùng bằng 1 thỏa mãn bài toán là F[n-1] – F[n – k – 1] . Vậy Ta có công thức quy hoạch động: F[n]:=2*F[n-1]-F[n-k-1]. 3 Bài Toán 3: LÁT VIỀN Tên chương trình: TILE.PAS Đề bài: Đường viền trang trí ở nền nhà có kích thước 2xN được lát bằng 2 loại gạch: loại kích thước 1x2 và loại 2x2. Hãy xác định số cách lát khác nhau có thể thực hiện. Dữ liệu: Vào từ file văn bản TILE.INP, gồm nhiều dòng, mỗi dòng chứa một số nguyên N (1 < N ≤ 250). Kết quả: Đưa ra file văn bản TILE.OUT các kết quả tìm được, mỗi số trên một dòng. Ví dụ: TILE.INP 2 8 12 100 200 TILE.OUT 3 171 2731 845100400152152934331135470251 107129202950599351702797472822744173501480199585519522353425 1 Xây dựng giải thuật: Đương nhiên không thể liệt kê tất cả các cách lát rồi đếm bởi vì số cách lát quá lớn. Tuy nhiên khi để ý rằng mỗi cách lát, vị trí 1x2 cuối cùng của đường viền chỉ có thể bị phủ bởi một viên gạch 1x2 “đứng” , một viên gạch 2x2 hoặc 2 viên gạch 1x2 đặt “nằm”, ở đây “đơn vị dữ liệu cuối” của ta là cách đặt gạch lát vị trí cuối đường viền. Từ đó chúng ta lại nghĩ đến chuyện sẽ tính số cách lát đường viền độ dài n theo số cách lát đường viền ngắn hơn như sau: Gọi F[k] là số lát viền kích thước 2*k. Bước cơ sở: Ta thấy ngay F[1] = 1; F[2] = 3. Bước quy nạp: + Nếu vị trí cuối cùng là 1 viên gạch 1x2 “đứng”: số cách lát bằng số cách lát viền kích thước 2*(k-1) và bằng F[k-1]. + Nếu vị trí cuối cùng là 1 viên gạch 2*2 hay 2 viên gạch 1x2 xếp “nằm”: số cách lát bằng số cách lát viền kích thước 2*(k-2) và bằng F[k-2]. Vậy F[k] = F[k-1] + 2*F[k-2]. Chú ý khi viết chương trình: + F[n] rất lớn nên phải thực hiện tính toán với số lớn. + Chỉ cần dùng ba biến tính luân phiên như BT1 4 Bài Toán 4: NHÓM Tên chương trình: GROUP.PAS Đề bài: Cho đồ thị vô hướng n đỉnh {1, 2, 3, …, n}(1 ≤ n ≤ 76) có dạng sau: Không có 2 đỉnh nào trong tập có đường nối trực tiếp, Không thể bổ sung đỉnh mới vào tập mà vẫn đảm bảo điều kiện đầu. Ví dụ, với n = 5 ta có thể có các tập tối đa là {1,3,5},{2,4},{2,5},{1,4}. Hai tập rời khác nhau, nếu khác nhau ít nhất một phần tử. Yêu cầu: Cho n. Hãy xác định số tập rời tối đa có thể xác định. Dữ liệu: Vào từ file văn bản GROUP.INP gồm nhiều tests, mỗi test là một số nguyên, cho trên một dòng. Kết quả: Đưa ra file văn bản GROUP.OUT, mỗi kết quả là một số nguyên, đưa ra trên một dòng. GROUP.INP 1 2 3 4 5 30 GROUP.OUT 1 2 2 3 4 4410 Xây dựng giải thuật: Nhận xét rằng: do điều kiện thứ nhất trong tập rời tối đa không thể có hai số liên tiếp, do điều kiện thứ hai trong tập rời tối đa hai số liên tiếp cách nhau không quá 3 đơn vị. Như thế nghĩa là nếu một tập rời tối đa được sắp tăng dần: a1< a2 < a3<…< ak-1< ak <… thì ak = ak-1 +2 hoặc ak = ak-1 + 3. Chúng ta xác định “đơn vị dữ liệu cuối” là giá trị phần tử cuối cùng của tập rời tối đa. Nếu gọi F[k] là số tập rời tối đa của {1,2,…, k} có chứa (đỉnh) k. Ta có: Bước cơ sở: F [1] = 1 (chỉ có tâp {1}); F [2] =1; (chỉ có tập {2}). F [3] = 1 (chỉ có tập {1, 3}). Bước quy nạp: Giả sử ta đã tính được số tập tối đa F[i] với i:=1,2,…k-1. Ta sẽ tính F[k]: Do đứng trước k chỉ có thể là k-2 hay k-3 nên: + số tập tối đa có đỉnh trước k là k – 2 bằng F[k – 2] + số tập tối đa có đỉnh trước k là k – 2 bằng F[k – 3] Vậy F[k] = F[k-3] + F[k-2]. 5 Cuối cùng, trong tập tối không thể không có cả đỉnh n và n-1 ngoài ra nếu chứa đỉnh n-1 thì không chứa đỉnh n và ngược lại. Do đó tổng số tập tối đa có thể có với n đỉnh là: F[n-1] + F[n]. 6 Bài Toán 5: Dãy đơn điệu dài nhất. Đề bài: Cho dãy N số nguyên a1, a2,..., aN, tìm độ dài dãy con tăng dài nhất của dãy đã cho. Xây dựng giải thuật: Đây là bài toán cơ bản mà bất cứ tài liệu nào khi mô tả phương pháp quy hoạch động đều lấy làm ví dụ. Khi xét đến số hạng a k làm đơn vị dữ liệu cuối của một dãy con tăng ta phải thêm ak vào sau một dãy con tăng dài nhất có thể ở phía trước (“có thể” ở đây bao hàm cả việc các phần tử của dãy con đó phải nhỏ hơn ak). Gọi F[i] là độ dài dãy con tăng dài nhất có số hạng cuối là a[i]. Bước cơ sở: F[1] = 1; Bước quy nạp: vói k > 1, F[k] = max{F[i] : i < k, ai < ak} + 1. Chú ý khi viết chương trình: Khi không có ai < ak thì F[k] =1. Bài Toán 6 (Mở rộng): Tính số lượng các dãy con tăng dài nhất trong dãy đã cho. Giải quyết bài toán mở rộng này có ý nghĩa sâu sắc trong việc rèn luyện tư duy quy hoạch động cho học sinh. Ở đây ta có nhận xét quan trọng rằng: ai1, ai2, ..., aik là dãy con tăng dài nhất thì mỗi đoạn đầu liên tiếp của nó: a i1, ai2, ..., aip (p<=k) sẽ là dãy con tăng dài nhất có số hạng cuối là aip như vậy có nghĩa p là độ dài dãy con tăng này nên nó phải bằng F[ip] (mảng F nói trên). Từ đó ta sẽ tính số dãy con tăng T[i] có độ dài F[i] và số hạng cuối cùng là a i. Rõ ràng ai lúc này chỉ được thêm vào sau số hạng aj bé hơn nó mà F[j] +1 =F[i]. Khi ấy tâp các dãy con tăng độ dài F[i] kết thúc tại a[i] được bổ xung thêm T[i] phần tử. Vậy ở đây ta có công thức quy hoạch động như sau: T[i] = Tổng các T[j] với j thỏa mãn: j < i; a[j] < a[i]; F[j] + 1 = F[i]. điều này có nghĩa là để tính T[i] ta phải tính trước các F[j], tất nhiên việc này sẽ kết hợp tính song song trong cùng một vòng lăp. Kết quả cuối cùng là tổng các T[i] mà F[i] = max{F[j] : j = 1,2,...,n}. Bài Toán 7: ROBOT CỨU HỎA (Bài thi HSG Quốc Gia 2007) Đề bài: Trên một mạng lưới giao thông có n nút, các nút được đánh số từ 1 đến n và giữa hai nút bất kỳ có không quá một đường nối trực tiếp (đường nối trực tiếp là một đường hai chiều). Ta gọi đường đi từ nút s đến nút t là một dãy các nút và các đường nối trực tiếp có dạng: s = u1, e1, u2,..., ui, ei, ui+1, ..., uk-1, ek-1, uk = t, trong đó u1, u2, …, uk là các nút trong mạng lưới giao thông, ei là đường nối trực tiếp giữa nút ui và ui+1 (không có nút uj nào xuất hiện nhiều hơn một lần trong dãy trên, j = 1, 2, …, k). 7 Biết rằng mạng lưới giao thông được xét luôn có ít nhất một đường đi từ nút 1 đến nút n. Một robot chứa đầy bình với w đơn vị năng lượng, cần đi từ trạm cứu hoả đặt tại nút 1 đến nơi xảy ra hoả hoạn ở nút n, trong thời gian ít nhất có thể. Thời gian và chi phí năng lượng để robot đi trên đường nối trực tiếp từ nút i đến nút j tương ứng là tij và cij (1 ≤ i, j ≤ n). Robot chỉ có thể đi được trên đường nối trực tiếp từ nút i đến nút j nếu năng lượng còn lại trong bình chứa không ít hơn cij (1 ≤ i, j ≤ n). Nếu robot đi đến một nút có trạm tiếp năng lượng (một nút có thể có hoặc không có trạm tiếp năng lượng) thì nó tự động được nạp đầy năng lượng vào bình chứa với thời gian nạp coi như không đáng kể. Yêu cầu: Hãy xác định giá trị w nhỏ nhất để robot đi được trên một đường đi từ nút 1 đến nút n trong thời gian ít nhất. Dữ liệu: Vào từ file văn bản ROBOT.INP Dòng đầu tiên chứa một số nguyên dương n (2 ≤ n ≤ 500); Dòng thứ hai chứa n số, trong đó số thứ j bằng 1 hoặc 0 tương ứng ở nút j có hoặc không có trạm tiếp năng lượng (j = 1, 2, …, n); Dòng thứ ba chứa số nguyên dương m (m ≤ 30000) là số đường nối trực tiếp có trong mạng lưới giao thông; Dòng thứ k trong số m dòng tiếp theo chứa 4 số nguyên dương i, j, tij, cij (tij, cij ≤ 104) mô tả đường nối trực tiếp từ nút i đến nút j, thời gian và chi phí năng lượng tương ứng. Hai số liên tiếp trên một dòng trong file dữ liệu cách nhau ít nhất một dấu cách. Kết quả: Ghi ra file văn bản ROBOT.OUT một số nguyên dương w tìm được. Ví dụ: ROBOT.INP 4 0110 5 1254 1343 1494 2441 3452 ROBOT.OUT 3 Xây dựng giải thuật Đầu tiên đương nhiên ta phải tìm thời gian ít nhất có thể đi từ nút 1 đến nút n. Điều này không có gì khó khăn, chúng ta dùng giải thuật Dijkstra để tìm thời gian tối 8 thiểu T[i] cần có cho mỗi nút i mà từ nút 1 có thể đến được nút i trong thời gian T[i]. Sau đó với nhận xét rằng trên 1 đường đi tốn ít thời gian nhất: i 1 i2 ... ik hiển nhiên T[i1] < T[i2] < ... < T[ik]. Vì vậy ta sắp xếp lại các đỉnh theo chiều tăng dần của các T[i]. Bây giờ nhận xét rằng: thời gian đi từ nút 1 đến mỗi nút trên một đường đi tối ưu về thời gian cũng là tối ưu. Do đó ta sử dụng ý tưởng đã dùng ở bài toán trên nhưng thay vì tính số lượng đường đi có thời gian tối ưu đến mỗi nút i ta cập nhật giá trị nhỏ nhất W[i] của bình xăng cần có để đến được nút đó, lưu trữ thêm D[i] là xăng còn trong bình khi ra khỏi đỉnh i: Với mỗi nút pi (là nút thứ i sau khi đã sắp xếp): Tìm các nút pj với j < i mà: pj có đường nối tới pi và T[pj] + t[pj,pi] = T[pi]. Lúc đó: W[i] = W[j] + max{C[pj,pi] - D[j], 0} (Vì nếu xăng còn trong bình D[j] > C[pj,pi] thì không cần bình to hơn) D[i] = W[i] nếu pi là trạm xăng = max{D[pj] – C[pj,pi], 0} nếu pi không là trạm xăng. Kết quả cuối cùng là W[pi] với pi = n (do vậy ta chỉ tính toán đến lúc gặp pi = n). Bài Toán 8: Nối mạng máy tính. Đề bài: Các học sinh mỗi khi đến thực tập trong phòng máy tính thường hay chơi trò chơi trên mạng. Để ngăn ngừa, người trực phòng máy đã ngắt tất cả các máy ra khỏi mạng và xếp chúng thành một dãy trên một cái bàn dài và gắn chặt máy xuống mặt bàn rồi đánh số các máy từ 1 đến N theo chiều từ trái sang phải. Các học sinh tinh nghịch không chịu thua, họ đã quyết định tìm cách nối các máy trên bàn bởi các đoạn cáp nối sao cho mỗi máy được nối ít nhất với một máy khác. Để tiến hành công việc này, họ đã đo khoảng cách giữa hai máy liên tiếp. Bạn hãy giúp các học sinh này tìm cách nối mạng thỏa mãn yêu cầu đã nêu sao cho tổng độ dài cáp nối phải sử dụng là nhỏ nhất. Dữ liệu: Vào từ file văn bản CABLE.INP: Dòng đầu tiên chứa số lượng máy N (1 ≤ N ≤ 25000); Dòng thứ i trong số N-1 dòng tiếp theo chứa khoảng cách từ máy i đến máy i+1 (i=1, 2, …, N-1). Biết rằng khoảng cách từ máy 1 đến máy N không vượt quá 106. Kết quả: Ghi ra file văn bản CABLE.OUT độ dài của cáp nối cần sử dụng. Ví dụ: CABLE.INP CABLE.OUT 6 2 2 3 2 2 7 9 Xây dựng giải thuật: Nhận thấy rằng: để tổng độ dài cáp nhỏ nhất thì ta không thể nối dây giữa các máy không liên tiếp; mỗi đơn vị dữ liêu là một máy, đơn vị dữ liệu cuối khi xét đến máy thứ k chính là máy này. Trong cách nối tối ưu máy thứ k có thể nối hoặc không nối với máy thứ k-1 mà vẫn thỏa mãn mỗi máy được nối với ít nhất một máy khác. Gọi D[k] là khoảng cách giữa máy K-1 và máy K; Link[K] là độ dài nhỏ nhất nối K máy đầu và K-1 nối với K; NotLink[K] là độ dài nhỏ nhất nối K máy đầu và K-1 không nối với K. Khởi tạo giá trị NotLink[1]:=0; Link[1]:=+∞ {+∞ ở đây có thể lấy là 107}. Khi đó với mỗi K từ 2 đến N ta làm đồng thời hai công việc sau: Nếu máy K được nối với máy K-1 thì máy K-1 nối hoặc không nối K-2 cũng đươc: Link[K]:=min{Link[K-1];NotLink[K-1]} + D[K]; Nếu máy K không nối với máy K-1 thì máy K-1 phải nối với máy K-2: NotLink[K]:=Link[K-1]; Do máy thứ nhất phải nối với máy thứ hai, máy thứ N-1 phải nối với máy thứ N kết quả là Link[N]. Cải tiến: Ta thấy qua mỗi bước ta chỉ cần giữ lại 2 giá trị cuối của Link và NotLink nên ta có thể dùng 2 biến L và NL để thay thế cho 2 mảng. Như vậy ta còn có thể dùng biến D để thay cho mảng D. Khi đó ta chỉ dùng biến chạy K từ 2 đến N và biến tg vừa đọc dữ liệu vừa xử lý: Readln(f,D); tg:=NL; NL:=L; L:=min{tg;L} + D; Chú ý: Khoảng cách giữa các máy tối đa là 106 nên phải khai báo D là longint và tổng khoảng cách có thể hơn 1010 vì vậy phải khai báo L, NL là int64. Bài Toán 9: Bờm uống rượu. Đề bài: Bờm thắng phú ông trong một cuộc đánh cược và buộc phú ông phải đãi rượu. Phú ông bèn bày ra một dãy n chai chứa đầy rượu, và nói với Bờm rằng có 10 thể uống bao nhiêu tuỳ ý, nhưng đã chọn chai nào thì phải uống hết và không được uống ở ba chai liền nhau bởi đó là điều xui xẻo. Bạn hãy chỉ cho Bờm cách uống được nhiều rượu nhất. Dữ liệu: Vào từ file văn bản BOTTLES.INP Dòng đầu: ghi số nguyên dương n (n ≤ 100 000) Các dòng tiếp ghi số nguyên dương (≤ 100 000) là dung tích của các chai rượu phú ông bày ra, theo thứ tự liệt kê từ chai thứ nhầt từ chai thứ n, các số được ghi cách nhau bởi dấu cách hoặc dấu xuống dòng. Kết quả: Ghi ra file văn bản BOTTLES.OUT Dòng đầu: Ghi số chai được chọn và lượng rượu tối đa có thể uống cách nhau một dấu cách. Các dòng tiếp theo, mỗi dòng ghi chỉ số của một chai chọn ra được. Xây dựng giải thuật: Mỗi đơn vị dữ liệu là một chai rượu, khi xét đến đơn vị dữ liệu cuối là chai rượu thứ K Bờm có thể uống hoặc không. Gọi Drink[K] là lượng rượu tối đa uống được ở K chai đầu mà không uống K; NotDrink[K] là rượu tối đa uống ở K chai đầu và có uống chai thứ K. Khởi tạo NotDrink[1]:=0; Drink[1]:=A[1]. Khi đó với mỗi K từ 2 đến N: Bờm không uống chai thứ K thì có thể uống hoặc không uống chai K-1: NotDrink[K]:=max{NotDrink[K-1];Drink[K-1]}; Bờm uống chai thứ K thì không uống chai K-1 hoặc uống chai K-1 nhưng không uống chai K-2: Drink[K]:=max{NotDrink[K-1];NotDrink[K-2] + A[K-1]} + A[K]; Cải tiến: Ta thấy qua mỗi bước ta chỉ cần giữ lại 2 giá trị cuối của NotDrink và Drink nên ta có thể dùng 4 biến D, ND1 và ND2 để thay thế cho 2 mảng. Như vậy ta còn có thể dùng 2 biến A, A1 để thay cho mảng A. Khi đó ta chỉ dùng biến chạy K từ 2 đến N và biến tg vừa đọc dữ liệu vừa xử lý: Readln(f,A); tg:=ND1; ND1:=max{ND1;D}; D:=max{tg;ND2 + A1} + A; A1:=A; ND2:=ND1; Chú ý khi viết chương trình: Lượng rượu mỗi chai tối đa là 10 5 nên phải khai báo A là longint và tổng lượng rượu có thể hơn 5.109 vì vậy phải khai báo D, ND1, ND2 là int64. 11 Bài Toán 10: Trò chơi với băng số (HSG QG 2009). Đề bài: Trò chơi với băng số là trò chơi tham gia trúng thưởng được mô tả như sau: Có một băng hình chữ nhật được chia ra làm n ô vuông, đánh số từ trái qua phải bắt đầu từ 1. Trên ô vuông thứ i người ta ghi một số nguyên dương ai, i = 1, 2, ..., n. Ở một lượt chơi, người tham gia trò chơi được quyền lựa chọn một số lượng tùy ý các ô trên băng số. Giả sử theo thứ tự từ trái qua phải, người chơi lựa chọn các ô i1, i2, ..., ik. Khi đó điểm số mà người chơi đạt được sẽ là: ai1 - ai2 + ... + (-1)k-1aik  Yêu cầu: Hãy tính số điểm lớn nhất có thể đạt được từ một lượt chơi. Dữ liệu: Dòng đầu tiên chứa số nguyên dương n ( n ≤ 106 ) là số lượng ô của băng số; Dòng thứ hai chứa n số nguyên dương a1, a2, ..., an ( ai ≤ 104, i = 1, 2, ..., n ) ghi trên băng số. Các số liên tiếp trên cùng dòng được ghi cách nhau bởi ít nhất một dấu cách. Kết quả:Một số nguyên duy nhất là số điểm lớn nhất có thể đạt được từ một lượt chơi. Xây dựng giải thuật: Ta hình dung ra việc chọn lần lượt một dãy con để có được một tổng đan dấu lớn nhất. Mỗi đơn vị dữ liệu là một số hạng, số hạng a k – đơn vị dữ liệu cuối bước k có thể chọn mang dấu + hoặc –. Gọi FC[k] là tổng đan dấu lớn nhất mà số hạng cuối là a k, FT[k] là tổng đan dấu lớn nhất mà số hạng cuối là - ak . Ta có: FC[k] = max{FT[i] + A[k], i < k}; FT[k] = max{FC[i] – A[k], i < k}; Cải tiến: Việc tìm max{FT[i], i < k}; max{FC[i], i < k} được cập nhật ngay trong quá trình tính toán, vì vậy ta không cần hai mảng FT và FC mà chỉ cập nhật bằng hai biến F1, F2. Bài Toán 11: CẶP SỐ 0 Tên chương trình: PAIR.PAS Đề bài: Xuất phát từ xâu S ban đầu chỉ chứa một ký tự ‘1’, người ta biến đổi n lần theo quy tắc sau: 12  Tạo xâu T bằng cách đảo các ký tự trong S: ‘1’ thành ‘0’ và ngược lại,  Tính S mới: S := T + S. Với cách biến đổi đó, ta có: n S 1 01 2 1001 3 01101001 Yêu cầu: Cho biết n (0 < n ≤ 1 000). Hãy xác định cặp số 0 trong xâu S sau n lần biến đổi. Dữ liệu: Vào từ file văn bản PAIR.INP gồm nhiều dòng, mỗi dòng chứa một số nguyên n. Kết quả: Đưa ra file văn bản PAIR.OUT, mỗi kết quả đưa ra trên một dòng dưới dạng số nguyên. Ví dụ: PAIR.INP PAIR.OUT 2 1 3 1 Xây dựng giải thuật: Do T là xâu bù của S và S:= T+S nên số lượng số cặp số 0 ở xâu mới được xác định như sau: + Số lượng cặp số 0 trong xâu S cũ; + Số lượng cặp số 0 trong xâu T = số lượng cặp số 1 trong xâu S cũ + x cặp số 0 tạo ra khi ghép 2 xâu S và T trong đó x=1 khi cuối xâu T và đầu xâu S cũ đều bằng 0, trường hợp ngược lại x=0. Ta thấy rằng kí tự kết thúc xâu S luôn là kí tự ‘1’ nên kí tự kết thúc xâu T luôn là ‘0’ do đó để tính x ta chỉ cần cập nhập lại biến d lưu kí tự đầu của xâu là ‘0’ hay là ‘1’. Gọi F[i] là số lượng cặp số 0, T[i] là số lượng cặp số 1 của S sau i lần biến đổi. Bước cơ sở: F[1]= T[1] = T[2] = 0; F[2] = F[3]=T[3] = 1; Bước quy nạp: F[i]:= T[i-1]+F[i-1]+x; T[i]:=T[i-1]+F[i-1]; Cải tiến giải thuật: Nhận thấy rằng để tính được F[i], T[i] ta chỉ cần biết F[i-1] và T[i-1] do đó thay vì dùng 2 mảng 1 chiều tốn bộ nhớ ta chỉ cần dùng 2 biến để lưu giá trị của 13 F[i-1] và T[i-1] là F1 và T1, cùng với 2 biến để lưu giá trị của F[i] và T[i] là F2 và T2. Mỗi lần biến đổi ta tính S2 và T2 theo S1 và T1 sau đó gán F1:=F2; T1:=T2; Chú ý khi viết chương trình: Tuy nhiên chương trình trên mới chỉ chạy được với kích thước n tối đa là 65. lý do là kết quả rất lớn các dữ liệu số đang sử dụng không lưu trữ nổi. Để chạy được với kích thước tối đa cỡ n=1000 ta cần tạo dữ liệu mới với các phép tính số lớn. Bài Toán 12: Nước ngựa đi (Đề thi Olympic Tin học trẻ Toàn quốc) Đề bài: Số điện thoại độ dài N (1≤ N ≤ 100), chọn theo cách đi của con mã, không được bắt đầu bằng 0 hoặc 8 . Bảng phím điện thoại được nêu ở hình bên. Ví dụ một số điện thoại hợp lệ độ dài 7: 3 40 49 27 . Yêu cầu : Tính số lượng số điện thoại hợp lệ độ dài N. Ví dụ: N=2 Kết quả :16. Xây dựng giải thuật: Một số điện thoại độ dài N là một “đường đi” của quân mã qua N ô, vì thế nó có được từ đường đi của quân mã qua N-1 ô cộng thêm một bước đi cuối cùng nữa. Đơn vị dữ liệu cuối ở đây chính là vị trí cuối cùng của con mã trên đường đi đó. Gọi F[k,i] là số lượng số điện thoại hợp lệ độ dài k và có chữ số cuối cùng là i. Bước cơ sở: F[1,i] = 1 với mọi i = 1, 2, 3, 4, 5, 6, 7, 9; F[1,0] = F[1,8]=0; Bước quy nạp: Nếu bước cuối cùng con mã ở ô số 0 thì trước đó nó chỉ có thể ở ô 4 hoặc 6 nên: F[k,0]:=F[k-1,4]+F[k-1,6]; Nếu bước cuối cùng con mã ở ô số 6 thì trước đó nó chỉ có thể ở ô số 7, 1 hoặc 0 nên: F[k,6]:=F[k-1,0]+F[k-1,1]+F[k-1,7]; Suy luận tương tự nhu vậy ta có công thức quy nạp với các i từ 0 đến 9 như sau: F[k,0]:=F[k-1,4]+F[k-1,6]; F[k,1]:=F[k-1,6]+F[k-1,8]; F[k,2]:=F[k-1,7]+F[k-1,9]; F[k,3]:=F[k-1,4]+F[k-1,8]; F[k,4]:=F[k-1,0]+F[k-1,3]+F[k-1,9]; F[k,5]:=0; (khi k > 1); F[k,6]:=F[k-1,0]+F[k-1,1]+F[k-1,7]; F[k,7]:=F[k-1,6]+F[k-1,2]; F[k,8]:=F[k-1,1]+F[k-1,3]; F[k,9]:=F[k-1,4]+F[k-1,2]; Kết quả bài toán là tổng tất cả các các F[N,i] với I = 1, 2, …, 9. Bài Toán 13: NHẢY VỀ ĐÍCH Tên chương trình: JUMP.PAS Đề bài: Xét bảng kích thước nn ô vuông (4 ≤ n ≤ 100), trên mỗi ô ghi một số nguyên trong phạm vi từ 0 đến 9. Ở góc trên trái có một quân cờ. Ta phải chuyển quân cờ về ô dưới phải của bảng theo các quy tắc sau: 14  Chỉ được di chuyển trên một hàng sang phải hay xuống dưới theo một cột,  Số ghi trên ô có quân cờ kích thước bước nhảy,  Chỉ được di chuyển trong phạm vi bảng đang xét. Với một bảng cho trước, có thể không có cách nhảy từ ô trên trái về ô dưới phải hoặc có nhiều cách. Ví dụ, với bảng cho ở hình dưới, ta có 3 cách khác nhau nhảy về đích. Yêu cầu: Cho n và các số trên bảng. Hãy xác định số cách nhảy khác nhau về đích. Dữ liệu: Vào từ file văn bản JUMP.INP:Dòng đầu tiên chứa số nguyên n, n dòng sau; mỗi dòng chứa n số nguyên mô tả một dòng của bảng theo thứ tự từ trên xuống dưới. Kết quả: Đưa ra file văn bản JUMP.OUT một số nguyên duy nhất – số cách nhảy. Xây dựng giải thuật: Suy nghĩ đầu tiên là đường đi từ ô (1;1) đến ô (N;N) cũng là một dãy các ô tương tự đường đi của con mã trong bài toán trên, có điều quy luật di chuyển của quân cờ này khác con mã. Mặc dù vậy ta hoàn toàn có thể sử dụng ý tưởng trong cách tính số đường đi của con mã để tính số đường đi của quân cờ này: Ta sẽ tính số cách đi của quân cờ từ ô (1;1) đến mọi ô khác lần lượt trên các dòng từ 1 đến N từ trái sang phải. Khi đó đơn vị dữ liệu cuối chính là ô cuối cùng của mỗi đường đi. Gọi F[i,j] là số cách nhảy khác nhau từ ô [1,1] đến ô [i,j] theo quy tắc. Kết quả cuối cùng là F[N,N]. Các F[i,j] được tính lần lượt từ trên xuống dưới từ trái sang phải. Nhận xét tương tự bài toán quân mã rằng để đến được ô [i,j] thì trước đó quân cờ phải đứng ở một trong các ô [p,q] thỏa mãn: p = i (cùng hàng) và q + a[p,q] = j; hoặc q = j ( cùng cột ) và p + a[p,q] = i; Khi đó F[i,j] là tổng các F[p,q] thỏa mãn một trong hai điều kiện trên: 15 Bước cơ sở: F[1,1] = 1; F[i,j] = 0 khi i<=0 hoặc j<= 0; Bước quy nạp: Theo cột: for p:=i-1 downto i-9 do {do a[p,q] không vượt quá 9} if a[p,j]=(i-p) then {nhảy được từ ô[p,j] đến ô [i,j]} F[i,j]:=F[i,j]+F[p,j]; Theo hàng: for q:=j-1 downto j-9 do if a[i,q]=(j-q) then {nhảy được từ ô [i,q] đến ô [i,j] } F[i,j]:=F[i,j]+F[i,k]; Phải khai báo các các phần tử lính canh bên ngoài mảng F bằng 0 để câu lệnh truy cập mảng a và mảng F không bị lỗi tràn vùng nhớ. Cải tiến giải thuật: Thay vì tính số cách nhảy từ ô [1,1] đến ô [N,N] với ràng buộc chỉ được nhảy từ trên xuống dưới từ trái sang phải thì ta làm ngược lại tính số cách nhảy từ ô [N,N] đến ô [1,1] với ràng buộc chỉ đươc nhảy từ dưới lên trên từ phải sang trái. Kết quả cuối cùng sẽ là F[1,1] (cho kết quả tương tự cách làm trên). Các F[i,j] sẽ được tính lần lượt từ dưới lên trên từ phải sang trái nhưng không được tính lại F[N,N] (vì F[N,N] đã đươc khởi tạo bằng 1). Ta có công thức truy hồi để tính mỗi F[i,j] như sau: F[i,j]:=F[i,j+a[i,j]] + F[i+a[i,j],j]. Phần chính của chương trình sẽ rất ngắn gọn : for i:=n downto 1 do for j:=n downto 1 do if (i<>n) or (j<>n) then {Để tránh tính lại F[N,N]} F[i,j]:=F[i,j+a[i,j]] + F[i+a[i,j],j]. Chú ý khi lập trình: ta nên khai báo mảng F [-9..Nmax+9,-9..Nmax+9] để không phải xử lý riêng một số trường hợp. Ban đầu khởi tạo mảng F bằng 0 riêng F[1,1] (ở cách thứ nhất) hoặc F[N,N] (cách thứ hai) bằng 1. Bài Toán 14: Ô TÔ BUÝT Tên chương trình: BUS.??? Đề bài: Đường trong thành phố Bytecity đều chạy từ Bắc xuống Nam hay từ Tây sang Đông tạo thành một lưới ô vuông. Các đường chạy từ Bắc xuống Nam được đánh số từ 1 tới n từ Tây sang Đông, các đường chạy từ Tây sang Đông được đánh số tự 1 tới m từ Nam lên Bắc. Nút giao thông (i, j) là giao giữa đường Bắc – Nam thứ i với đường Tây – Đông thứ j. Mỗi nút giao thông là một trạm chờ ô tô buýt. Buổi sáng sớm ô tô buýt đón học sinh đi học sẽ chạy từ nút (1, 1) tới nút (n, m). Ô tô chỉ chạy 16 theo hướng Bắc và/ hoặc Đông. Người lái chuyến đầu tiên đa đi theo con đường cho phép đón được nhiều học sinh nhất. Yêu cầu: Cho biết n, m (1 ≤ n, m ≤ 1000), số nút k có học sinh đứng chờ (1 ≤ k ≤ 1000), toạ độ mỗi nút và số người chờ ở đó. Hãy cho biết chuyến đầu tiên có thể đón được bao nhiêu học sinh (giả thiết không hạn chế số người lên xe). Số người chờ ở mỗi nút khồn quá 106 và tổng số người chờ không quá 109. Dữ liệu: Vào từ file văn bản BUS.INP: Dòng đầu tiên chứa 3 số nguyên n m k, k dòng sau: mỗi dòng chứa 3 số nguyên i, j và p, trong đó i, j – toạ độ nút, p – số người chờ. Kết quả: Đưa ra file văn bản BUS.OUT một số nguyên – số lượng học sinh nhiều nhất đón được. Xây dựng giải thuật: Đây lại là một bài toán xác định đường đi (tối ưu) có quy luật di chuyển cho các bước đi, đơn vị dữ liệu cuối là nút cuối của đường đi. Ta tính F[i,j] là số lượng học sinh đã đón được nhiều nhất khi xe ở nút (i,j); a[i,j] là số lượng học sinh đứng chờ tại nút (i,j). Vì ô tô chỉ chạy theo hướng Bắc hoặc Đông nên khi xem nút (i,j) là đơn vị dữ liệu cuối thì trước đó ô tô chỉ có thể ở nút (i-1,j) hoặc (i,j-1). Do đó ta sẽ tính các F[i,j] lần lượt theo từng dòng từ dưới lên trên, từ trái sang phải: Bước cơ sở: F[1,1]:= a[1,1]; Bước quy nạp: F[i,j]:=max(F[i-1,j],F[i,j-1])+a[i,j]; Kết quả yêu cầu chính là F[n,m]. Cải tiến giải thuật: Để tính F[i,j] ta cần biết F[i-1,j] và F[i,j-1] do đó ta không cần lưu lại toàn bộ mảng F mà chỉ cần 2 dòng ứng với 2 mảng một chiều F[0..1,0..1000] of longint là đủ. Ta sẽ tính n lần F[1,i] theo F[0,i] với i=1..n; sau mỗi lần tính ta gán lại F[0,i]:=F[1,i]. Ngoài ra còn có thể tăng tốc độ cho chương trình bằng cách tránh việc sao chép từ F[1,i] sang F[0,i]bàng cách sử dụng “con lắc” hoán đổi vị trí của F[0,i] và F[1,i]. Bài Toán 15: LÒ CÒ (Bài thi HSG QG 2008) Tên chương trình JUMP.PAS Đề bài: Nhảy lò cò là trò chơi dân gian của Việt Nam. Người trên hành tinh X cũng rất thích trò chơi này và họ đã cải biên trò chơi này như sau: Trên mặt phẳng vẽ n vòng tròn được đánh số từ 1 đến n. Tại vòng tròn i người ta điền số nguyên 17 dương ai. Hai số trên hai vòng tròn tùy ý không nhất thiết phải khác nhau. Tiếp đến người ta vẽ các mũi tên, mỗi mũi tên hướng từ một vòng tròn đến một vòng tròn khác. Quy tắc vẽ mũi tên là: Nếu có ba số a i, aj, ak thỏa mãn ak = ai + aj thì vẽ mũi tên hướng từ vòng tròn i đến vòng tròn k và mũi tên hướng từ vòng tròn j đến vòng tròn k. Người chơi chỉ được di chuyển từ một vòng tròn đến một vòng tròn khác nếu có mũi tên xuất phát từ một trong số các vòng tròn, di chyển theo cách mũi tên đã vẽ để đi đến các vòng tròn khác. Người thắng cuộc sẽ là người tìm được cách di chuyển qua nhiều vòng tròn nhất. Ví dụ: Với 5 vòng tròn và các số trong vòng tròn là 1, 2, 8, 3, 5, trò chơi được trình bày trong hình dưới đây: Khi đó có thể di chuyển được nhiều nhất qua 4 vòng tròn (tương ứng với đường di chuyển được tô đậm trên hình vẽ). Yêu cầu: Hãy xác định xem trong trò chơi mô tả ở trên, nhiều nhất có thể di chuyển được qua bao nhiêu vòng tròn. Dữ liệu: Dòng đầu chứa số nguyên n (3 ≤ n ≤ 1000); Dòng thứ hai chứa dãy số nguyên dương a1, a2, ..., an (ai ≤ 109, i=1, 2,..., n). Hai số liên tiếp trên một dòng được ghi cách nhau bởi dấu cách. Kết quả: Ghi ra số lượng vòng tròn trên đường di chuyển tìm được. Xây dựng giải thuật: Giả sử các số trong vòng tròn được cho trong mảng a[1..N]. Từ một vòng tròn sẽ chỉ có thể đi đến một vòng tròn ghi số lớn hơn, vì vậy ta sẽ sắp xếp lại mảng a (tương ứng với các vòng tròn) theo chiều tăng dần. Bây giờ ta có quy tắc di chuyển: từ vòng tròn i đến được vòng tròn j nếu a[j] = a[i] + a[k] với k <> i, k < j nào đó. Với quy tắc di chuyển này, mỗi đơn vị dữ liệu là một vòng tròn (ứng với một số trong dãy đã sắp xếp). Khi xét đơn vị dữ liệu cuối là vòng tròn thứ i, để nó là vị trí cuối của một dãy nhiều vòng tròn nhất ta thêm nó vào sau dãy dài nhất có thể các vòng tròn phía trước. Gọi F[i] là số lượng vòng tròn nhiều nhất có thể đi qua tới vòng tròn thứ i (tính cả vòng tròn thứ i). 18 Bước cơ sở: F[i] = 1 với mọi i= 1,2,…,N Bước quy nạp: Để tính F[i] ta thêm vòng tròn i vào sau dãy nhiều vòng tròn nhất đã đi qua ở phía trước, có nghĩa là tìm F[j] lớn nhất thỏa mãn điều kiện có đường đi từ vòng tròn j đến vòng tròn i, lúc đó F[i] = F[j] + 1. Như đã nêu, việc kiểm tra xem có đường đi từ vòng tròn j đến vòng tròn i chính là việc liểm tra xem có thể tách a[i] thành tổng a[j]+a[k], điều này có thể thực hiện nhanh chóng bằng tìm kiếm nhị phân giá trị a[i] – a[j] trong dãy a[1..j-1] Bài Toán 16: Hành trình đông tây Đề bài: Cho một bảng A kích thước m * n, trên đó ghi các số nguyên. Một người xuất phát tại một ô nào đó của cột 1, cần sang cột n (tại ô nào cũng được). Quy tắc: Từ ô A[i,j] chỉ được quyền sang một trong 3 ô A[i,j+1]; A[i+1,j+1], A[i-1,j+1]. Hãy tìm vị trí ô xuất phát và hành trình đi từ cột 1 sang cột n sao cho tổng các số ghi trên đường đi là lớn nhất. 1 2 6 7 9 7 6 5 6 7 A = 2 3 4 2 Nhận xét: Hoàn toàn 1 có thể xây dựng giải thuật 7 8 7 6 cho bài toán này 4 tương tự như bài toán trước. Tuy nhiên bài toán tương tự sau đây cần có những xử lý tinh tế hơn: Bài Toán 17: SĂN MỒI. Đề bài: Vợ chồng nhà Thạch Sùng tổ chức một cuộc đi săn muỗi trên một bức tường kích thước m*n được chia thành lưới ô vuông đơn vị. Các hàng của lưới được đánh số từ 1 đến m theo thứ tự từ trên xuống dưới và các cột được đánh số từ 1 đến n theo thứ tự từ trái qua phải. Trên mỗi ô (i,j) của bức tường có aij con muỗi. Vợ chồng Thạch Sùng đang đứng ở mép trên của bức tường, chúng có thể tùy chọn vị trí xuất phát để có thể bò xuống các ô bên dưới để ăn muỗi. Khi thạch sùng đi qua ô nào thì muỗi ở ô đó bị ăn hết. Do tường khá trơn nên từ 1 ô trên 1 hàng, thạch sùng chỉ có thể bò xuống ô ở hàng dưới có chung cạnh hoặc chung đỉnh với ô đang đứng. Khi thạch sùng đi xuống ô dưới của mép tường thì cuộc săn kết thúc.Như vậy hành trình săn mồi của một con thạch sùng bắt đầu từ ô xuất phát (trên hàng 1) có thể biểu diễn bằng một xâu gồm m-1 kí tự, trong đó kí tự thứ i thuộc {L,D,R} cho biết tại bước di chuyển thứ i thạch sùng bò sang ô trái dưới, bên dưới hay phải dưới. (xem hình) * L D R Vợ chồng Thạch Sùng đang tranh luận xem nên chia nhau ra săn mồi như thế nào để tổng số muỗi ăn được là lớn nhất. Bạn hãy dự tính số muỗi lớn nhất mà chúng có thể ăn được và chỉ ra hai đường đi săn mỗi tối ưu của 2 con Thạch Sùng. 19 Chú ý: Tại một thời điểm, hai con thạch sùng có thể ở cùng 1 ô. Số muỗi ăn được là tổng số muỗi trên các ô được đi qua. Dữ liệu: vào từ file văn bản HUNTING.INP Dòng 1 chứa 2 số nguyên dương m,n <100. m dòng tiếp theo dòng thứ i chưa n số nguyên, số thứ j là aij<100. Kết quả: ghi ra file văn bản HUNTING.OUT. Dòng 1 ghi tổng số muỗi 2 vợ chồng thạch sùng ăn được. Dòng 2 ghi chỉ xuất cột xuất phát của con thạch sùng thứ nhất và chỉ xuất cột xuất phát của con thạch sùng thứ hai. Dòng 3 ghi một xâu kí tự là hành trình của con thạch sùng thứ nhất. Dòng 3 ghi một xâu kí tự là hành trình của con thạch sùng thứ hai Ví dụ HUNTING.OUT HUNTING.OUT 44 0201 4052 0403 0202 23 24 LRD LRD Xây dựng giải thuật: Ta thấy sau mỗi bước vợ chồng Thạch Sùng di chuyển thì chúng sẽ chiếm 2 ô trên cùng một hàng (chỉ số cột 2 ô có thể trùng nhau) vì thế có thể coi đây là bài toán tìm đường đi của vợ chồng Thạch Sùng với đơn vị dữ liệu cuối ở bước thứ k là cặp ô trên dòng k mà vợ chồng thạch sùng chiếm chỗ. Chúng ta gọi f[k,i,j] là số muỗi ăn được nhiều nhất khi chúng đến dòng k và Thạch Sùng vợ ở cột i, còn chồng ở cột j. Rõ ràng để tới được ô [k,i] thì trước đó Thạch Sùng vợ phải ở một trong các ô ([k-1,i],[k-1,i-1],[k-1,i+1]), tương tự thì Thạch Sùng chồng cũng phải ở một trong các ô ([k-1,j],[k-1,j-1],[k-1,j+1]). Chính vì vậy ta có công thức truy hồi: f[k,i,j]=max(f[k-1,i,j], f[k-1,i-1,j],f[k-1,i+1,j], f[k-1,i,j-1], f[k-1,i-1,j-1],f[k-1,i+1,j-1], f[k-1,i,j+1],f[k-1,i-1,j+1],f[k-1,i+1,j+1])+M. Trong đó: M=a[k,i] + a[k,j] khi j khác k (vơ chồng Thạch Sùng ở khác ô). M=a[k,i] khi j = k (vợ chồng Thạch Sùng ở cùng ô). 20