Tài liệu Phương pháp quy hoạch động và vận dụng kết hợp giải các bài toán chuyên tin bậc thpt

ĐẠI HỌC ĐÀ NẴNG TRƯỜNG ĐẠI HỌC BÁCH KHOA  THÁI PHONG NGHĨA PHƯƠNG PHÁP QUY HOẠCH ĐỘNG VÀ VẬN DỤNG KẾT HỢP GIẢI CÁC BÀI TOÁN CHUYÊN TIN BẬC THPT Chuyên ngành: KHOA HỌC MÁY TÍNH Mã số: 60.48.01 TÓM TẮT LUẬN VĂN THẠC SĨ KỸ THUẬT Đà Nẵng – Năm 2018 Công trình được hoàn thành tại TRƯỜNG ĐẠI HỌC BÁCH KHOA Người hướng dẫn khoa học: PGS. TSKH. TRẦN QUỐC CHIẾN Phản biện 1: TS. ĐẶNG HOÀI PHƯƠNG Phản biện 2: TS. NGUYỄN THÁI SƠN Luận văn sẽ được bảo vệ trước Hội đồng chấm Luận văn tốt nghiệp thạc sĩ Khoa học máy tính họp tại Trường Đại học Bách khoa vào ngày 03 tháng 02 năm 2018. Có thể tìm hiểu luận văn tại:  Trung tâm Học liệu, Đại học Đà Nẵng tại Trường Đại học Bách khoa.  Thư viện Khoa Công nghệ thông tin, Trường Đại học Bách khoa – ĐHĐN. 1 MỞ ĐẦU 1. Lý do chọn đề tài Hiện nay nhiệm vụ phát hiện, đào tạo và bồi dƣỡng học sinh giỏi là một nhiệm vụ trọng tâm của các trƣờng THPT Chuyên của tất cả các tỉnh thành trong cả nƣớc, nhằm mục đích phát hiện bồi dƣỡng và đào tạo nhân tài, tạo ra một đội ngũ học sinh chất lƣợng cao làm tiền đề để phát triển nâng cao hơn nữa ở bậc đại học, sau đại học cho các em học sinh. Môn Tin học tự hào cũng là một môn học quan trọng không kém nên đƣợc đƣa vào chƣơng trình thi học sinh giỏi các cấp hằng năm nhƣ: thi học sinh giỏi cấp Tỉnh (thành phố), thi học sinh giỏi Olympic 30/04 (từ Đà Nẵng trở vào phía Nam), thi học sinh giỏi Quốc gia, bên cạnh đó còn có thi Tin học trẻ không chuyên (cấp Tỉnh và Toàn quốc). Trong vai trò là một giáo viên Tin học giảng dạy tại trƣờng THPT Chuyên Nguyễn Thiện Thành – TP Trà Vinh, hàng năm đều phải tham gia vào công tác bồi dƣỡng học sinh giỏi của bộ môn, cho đến nay qua nhiều năm bồi dƣỡng, bản thân tôi nhận thấy, trong cấu trúc của các đề thi học sinh giỏi môn Tin học, số lƣợng các bài toán trong một đề thi có thể giải bằng phƣơng pháp quy hoạch động thƣờng chiếm từ 30 – 70% của một đề thi, bởi khi ra đề thi ban tổ chức thƣờng rãi đều các chuyên mục của các phƣơng pháp nhƣ: duyệt, qui hoạch động và các thuật toán ứng dụng mô hình đồ thị, ... tuy nhiên trong đó có một số bài toán duyệt và ứng dụng mô hình đồ thị vẫn có thể áp dụng phƣơng pháp quy hoạch động để giải. Vì vậy có thể nói, quy hoạch động là một chuyên đề rất quan trọng mà mỗi học sinh thi tham gia đội tuyển học sinh giỏi đều phải nắm đƣợc nếu muốn đạt các thứ hạng cao ở các kỳ thi. 2 Với những lý do thiết thực đó, tôi xin chọn thực hiện đề tài: “PHƢƠNG PHÁP QUY HOẠCH ĐỘNG VÀ VẬN DỤNG KẾT HỢP GIẢI CÁC BÀI TOÁN CHUYÊN TIN BẬC THPT”. 2. Mục tiêu nghiên cứu Xây dựng và phân tích có hệ thống các bài tập có thể giải bằng phƣơng pháp Quy hoạch động, phân lớp chúng thành các lớp bài toán bằng cách nhận diện dựa trên kinh nghiệm của ngƣời học từ các bài toán quy hoạch động điển hình, kinh điển. Vận dụng kết hợp để giải các bài toán chuyên Tin trong công tác bồi dƣỡng học sinh giỏi môn Tin học. 3. Đối tƣợng và phạm vi nghiên cứu Phƣơng pháp quy hoạch động. Cấu trúc dữ liệu phù hợp để quy hoạch động. Các đề thi học sinh giỏi tin học các cấp. 4. Phƣơng pháp nghiên cứu Nghiên cứu lý thuyết về phƣơng pháp quy hoạch động, nhận dạng các bài toán có thể giải bằng phƣơng pháp quy hoạch động và phân tích các ƣu điểm của nó từ đó kết hợp thêm các phƣơng pháp khác để áp dụng giải các bài toán tối ƣu. Thiết kế thuật toán dựa trên phƣơng pháp quy hoạch động. 5. Ý nghĩa khoa học và thực tiễn của đề tài Ý nghĩa khoa học: Nghiên cứu và phân tích phƣơng pháp quy hoạch động. Vận dụng kết hợp vào việc giải các bài toán chuyên tin. Ý nghĩa thực tiễn: Giúp cho học sinh đạt kết quả cao hơn trong các kỳ thi học sinh giỏi Tin học. Làm tài liệu tham khảo để hỗ trợ cho học sinh giáo viên tin học dạy bồi dƣỡng chuyên tin. 3 CHƢƠNG 1: LÝ THUYẾT VỀ QUY HOẠCH ĐỘNG 1.1. Giới thiệu về phƣơng pháp quy hoạch động 1.1.1. Bài toán tối ưu 1.1.2. Nguyên lý Bellman 1.1.3. Bảng phương án 1.2. Nhận dạng bài toán quy hoạch động 1.3. Ƣu điểm của quy hoạch động 1.4. Các bƣớc thực hiện quy hoạch động 1.4.1. Xây dựng công thức truy hồi Giả sử bài toán mà ta cần tìm là chi phí tối ƣu dạng Max. Gọi Fi là giá trị lớn nhất khi xét đến phần tử thứ i. Tuy theo bài toán, ta có thể nhận ra các bài toán cơ sở của nó một cách rõ ràng và hiển nhiên. Thông thƣờng các giá trị này là F0 hoặc F1 hoặc F2 … Khởi tạo bằng cách gán các giá trị ban đầu cho chúng. Từ các giá trị ban đầu nêu trên, ta tăng dần số lƣợng các phần tử lên (tăng độ lớn của bài toán), tìm điểm chung trong cách tính các phần tử từ bài toán cơ sở (F0 hoặc F1) đến bài toán đang xét (Fi). Từ đó ta có đƣợc công thức truy hồi. Thông thƣờng công thức truy hồi có dạng: Fi = Max(Fi-1, Fi) {với i = 1 ... n} (*) Trong đó: - Fi là giá trị lớn nhất khi xét đến phần tử thứ i. - Max là hàm lấy giá trị lớn nhất của 1 trong các đối số của nó. - Fi-1 là bài toán con đã tối ƣu ở bƣớc liền kề trƣớc đó. - Fi-1 cũng đƣợc tính theo công thức Fi-1 = Max(Fi-2, Fi-1) - Và Fi-2 = Max(Fi-3, Fi-2) - … cho đến 4 - F1 - F0 1.4.2. Tổ chức dữ liệu và chương trình 1.4.3. Làm tốt (tối ưu thuật toán nếu được) 1.4.4. Truy vết tìm phương án tối ưu Thông thƣờng kết quả tối ƣu của một bài toán quy hoạch động là sau khi đã giải đƣợc bài toán sau cùng (bài toán thứ n, hay F n), nếu bảng phƣơng án là mảng 2 chiều thì hoặc là giá trị tối ƣu (GTTU) nằm ở cột cuối hoặc là GTTU nằm ở dòng cuối. Từ các vị trí chứa các GTTU đó, ta tiến hành truy vết ngƣợc trở về đi qua các bài toán con liền trƣớc nó cũng đã đạt đƣợc GTTU, cho đến khi trở về bài toán cơ sở ban đầu thì dừng. Vậy để có thể truy vết đƣợc thì ta phải tiến hành đánh dấu tại GTTU của bài toán thứ i mà ta đạt đƣợc. Cụ thể, khi tiến hành cài đặt công thức (*) ở trên, ta phải lƣu vết: If Fi-1 > Fi Then Begin Fi := Fi-1 Lƣu vết {chọn Fi-1} End Else Lƣu vết {không chọn Fi-1} 1.5. Các lớp bài toán quy hoạch động và ứng dụng 1.5.1. Dạng 1: Dãy con đơn điệu dài nhất 1.5.1.1. Mô hình 1.5.1.2. Công thức QHĐ 1.5.1.3. Cài đặt 1.5.1.4. Một số bài toán là biến thể cùng lớp của “dãy con đơn điệu dài nhất” 1.5.2. Dạng 2: Chia kẹo 5 1.5.2. 1. Mô hình 1.5.2. 2. Công thức 1.5.2. 3. Cài đặt 1.5.2. 4. Một số bài toán biến thể cùng lớp với bài toán “chia kẹo” 1.5.3. Dạng 3: Xâu con chung dài nhất 1.5.3. 1. Mô hình 1.5.3. 2. Công thức QHĐ 1.5.3. 3. Cài đặt 1.5.3. 4. Một số bài toán là biến thể cùng lớp của “Xâu con chung dài nhất” 1.5.4. Một số dạng khác: 1.6. Hạn chế của quy hoạch động CHƢƠNG 2: GIỚI THIỆU MỘT SỐ THUẬT TOÁN VÀ CẤU TRÚC DỮ LIỆU ĐỂ KẾT HỢP VỚI PHƢƠNG PHÁP QUY HOẠCH ĐỘNG 2.1. Bài toán 1: Phần thƣởng Tuấn là ngƣời chiến thắng trong một cuộc thi “tìm hiểu kiến thức vũ trụ” và đƣợc nhận các phần thƣởng do công ty XYZ tài trợ. Các phần thƣởng đƣợc bố trí trên một bảng hình vuông n x n có dạng một lƣới ô vuông kích thƣớc đơn vị. Các dòng của bảng đƣợc đánh số từ 1 đến n, từ trên xuống dƣới và các cột của bảng đƣợc đánh số từ 1 đến n, từ trái qua phải. Ô nằm trên giao của dòng i và cột j đƣợc gọi là ô (i,j) và trên ô đó chứa một món quà có giá trị là a[i,j] (1 <= i, j <= n) Để nhận phần thƣởng, Tuấn đƣợc phép chọn một hình vuông kích thƣớc k x k chiếm trọn trong một số ô của bảng và nhận tất cả các phần quà có trong các ô nằm trong hình vuông đó. Yêu cầu: Hãy xác định tổng giá trị lớn nhất của món quà mà Tuấn có thể nhận đƣợc. 6 Dữ liệu vào:  Dòng thứ nhất chứa hai sô nguyên dƣơng n, k (n <= 1000, n/3 <= k <= n).  Dòng thứ i trong số n dòng tiếp theo chứa n số nguyên dƣơng, số thứ j là a[i,j] (a[i,j] <= 1000) Kết quả: Ghi ra một số nguyên duy nhất là tổng giá trị lớn nhất của các món quà mà Tuấn có thể nhận đƣợc. Ví dụ: Dữ liệu vào: Kết quả: 43 86 1911 9999 1999 1 9 9 14 * Cách giải 1: Duyệt từng hình vuông có độ dài cạnh k, với i,j là cặp chỉ số góc trên bên trái hình vuông và x,y là góc dƣới phải hình vuông. Với mỗi hình vuông ta tiến hành tính tổng của chúng và so sánh với Max (Max ban đầu bằng - ∞). Độ phức tạp thuật toán là O(n4), không khả thi với yêu cầu của đề bài nếu n lớn. * Cách giải 2: Quy hoạch động Gọi F[i,j] là tổng các giá trị từ ô[1,1] tới ô[i,j]. Tính tất cả các F[i,j] theo công thức truy hồi sau: F[i,j]:=F[i,j-1] + F[i-1,j] + a[i,j] – F[i-1,j-1] ; Sau khi tính, bảng F[i,j] có dạng nhƣ sau: 1 10 11 12 10 28 38 48 11 38 57 76 12 48 76 109 Hình 2.2: Bảng lưu giá trị của F[i,j] bài toán “Phần thưởng” 7 Giải thích Giả sử ô đang tính F[3,3] đƣợc tính bằng công thức truy hồi: F[i,j]:=F[i,j-1] + F[i-1,j] + a[i,j] – F[i-1,j-1] ; F[3,3]:=F[3,2] + F[2,3] + a[3,3] – F[2,2]  F[3,3]:=38 + 38 + 9 – 28 = 57 Để tìm hình vuông lớn nhất có cạnh bằng k = 3 ta thực hiện nhƣ sau: Max:= - ∞ ; For i:=k to n do For j:=k to n do if Max < F[i,j] - F[i-k,j] - F[i,j-k] + F[i-k,j-k] then Max:= F[i,j] - F[i-k,j] - F[i,j-k] + F[i-k,j-k]; Bảng tính kết quả nhƣ sau: 1 10 11 12 10 28 38 48 11 38 57 76 12 48 76 109 Hình 2.3: Tìm giá trị hình vuông lớn nhất bài toán “Phần thưởng” Giải thích: Tìm hình vuông cạnh k có giá trị lớn nhất Max:= - ∞ ; Giả sử F[i,j] đang là F[4,4], để lấy hình vuông k = 3 thực hiện tính toán nhƣ sau: F[i,j] - F[i-k,j] - F[i,j-k] + F[i-k,j-k]  F[4,4] - F[1,4] - F[4,1] + F[1,1]  109 -12 - 12 + 1 = 86. Rồi so sánh giá trị này với Max để cập nhật giá trị lớn nhất cho Max. Vậy: theo cách giải này độ phức tạp lớn nhất chỉ là O(n2) 8 2.2. Bài toán 2: Đoạn con liên tiếp có tổng lớn nhất Cho dãy A gồm N số nguyên (N <= 100000). Tìm đoạn con (các phần tử liên tiếp) có tổng lớn nhất. Ví dụ: A = (2, 3, 4, -2) Kết quả là (2, 3, 4) với tổng là 9. *Cách giải 1: Duyệt vét cạn: Rất tự nhiên ta sử dụng một cặp chỉ số i và j để duyệt tất cả các đoạn con, với mỗi cặp i và j ta lần lƣợt tính tổng từ A[i] đến A[j]. Nhƣ vậy, độ phức tạp thuật toán trong trƣờng hợp này là O(n3). * Cách giải 2: Quy hoạch động Gọi F1[i] là tổng lớn nhất trong đoạn A[1..i] (có thể không chứa A[i]). Để tính đƣợc F1[i] ta dùng thêm 1 mảng phụ F2 với ý nghĩa: F2[i] là tổng lớn nhất trong đoạn A[1..i] có chứa A[i]. Cơ sở quy hoạch động: F1[0]=0 ; F2[0] = 0 ; Công thức truy hồi F2[i] = Max(F2[i - 1] + A[i], A[i]) F1[i] = Max(F1[i - 1], F2[i]) Dựa vào quan hệ giữa F1[i - 1] và F2[i] để tìm ra phần tử cuối của đoạn con cần tìm. Sau đó duyệt lui về 1 cho tới khi nào đạt đƣợc tổng lớn nhất (F1[n]). Độ phức tạp: O(n). 2.3 Quy hoạch động dựa trên bài toán đã đƣợc sắp xếp 2.3.1 Sắp xếp 2.3.2 Phát biểu bài toán 2.3.3 Các thuật toán sắp xếp thông dụng 2.3.3.1 Thuật toán sắp xếp nổi bọt (Bubble Sort) 2.3.3.2 Thuật toán sắp xếp nhanh (Quick Sort) 9 2.3.3.4 Sắp xếp bằng đếm phân phối (Distribution Counting) 2.3.3.5 Một số bài toán Sau đây là một số bài toán đòi hỏi phải sắp xếp trƣớc khi có thể quy hoạch động. Bài 1: Robot Một cuộc trình diễn sáng tạo robot có N robot tham gia (các robot đƣợc đánh số từ 1 đến N). Địa hình trình diễn là một sân phẳng đã đƣợc vạch thành N tuyến song song, mỗi tuyến là đủ dài để các robot có thể trổ tài. Tại vạch xuất phát, mỗi tuyến đều có gắn 1 bảng điện tử cho biết tọa độ của robot trên tuyến tƣơng ứng. Tọa độ này là những số nguyên biểu thị khoảng cách robot đến vạch xuất phát. Tại thời điểm G, tọa độ của robot i đang là ai (i=1,2,...,N), Ban tổ chức công bố một bộ gồm M thẻ lệnh, mỗi thẻ ghi một số nguyên bj (j=1,2,...,M) và yêu cầu các robot phải phối hợp phân công để mỗi robot đƣợc nhận một thẻ rồi đi chuyển đến tọa độ ghi trong thẻ. Chi phí mà một robot di chuyển từ từ tọa độ x đến tọa độ y đƣợc tính là giá trị tuyệt đối của hiệu a-b. Ban tổ chức sẽ đánh giá độ thông minh của các robot thông qua tổng chi phí S mà các robot phải chi phí cho việc di chuyển, theo tiêu chí: S càng nhỏ thì cảng đƣợc đánh giá cao. Yêu cầu: Cho biết tọa độ tại thời điểm G của N robot, M giá trị ghi trong M thẻ lệnh của ban tổ chức, hãy cho biết giá trị nhỏ nhất của S mà các robot có thể đạt đƣợc. Dữ liệu + Dòng đầu tiên ghi lần lƣợt hai số nguyên dƣơng M, N(1<=N<=M<=1000). + Dòng thứ 2 ghi M số nguyên b1, b2, ...,bM. + Dòng thứ 3 ghi N số nguyên a1, a2, ...,aN. 10 Tất cả các số ai, bj, đều nguyên và nằm trong khoảng từ 0 đến 10000. Kết quả: Ghi ra duy nhất số nguyên S tìm đƣợc Ví dụ: ROBOT.INP 65 510203 20141 ROBOT.OUT 2 Thuật toán quy hoạch động nhƣ sau  Sắp xếp mảng tọa độ a, b tăng dần (Dùng Quick Sort)  Gọi F[i,j] là chi phí nhỏ nhất để i robot di chuyển trong j vị trí cho trƣớc: Vì đã sắp xếp trƣớc tọa độ của các robot và các thẻ nên: - Ta có: F[0,0]=0; F[0,1]=0; F[0,2]=0; Trƣờng hợp 1: 1 robot và nhiều thẻ - Nếu có 1 robot và 1 thẻ thì : F[1,1]=F[0,0] + abs(a[1]-b[1]) - Nếu có 1 robot và 2 thẻ thì F[1,2]=min (F[1,1], F[0,1] + abs(a[1]-b[2])) - Nếu có 1 robot và 3 thẻ thì F[1,3]=min (F[1,2], F[0,2] + abs(a[1]-b[3])) - ... Trƣờng hợp 2: nhiều robot và nhiều thẻ - Nếu có 2 robot và 2 thẻ thì F[2,2]=F[1,1] + abs(a[2]-b2]) - Nếu có 2 robot và 3 thẻ thì F[2,3]=min (F[2,2], F[1,2] + abs(a[2]-b[3])) - Nếu có 2 robot và 4 thẻ thì F[2,4]=min (F[2,3], F[1,3] + abs(a[2]-b[4])) 11 -… Từ đó ta suy ra công thức truy hồi F[i,i]:= F[i-1,i-1] + abs(x[i] – y[i]), với mọi i trong khoảng [1..n] F[i,j]:= min(F[i,j-1], F[i-1,j-1] + abs(x[i] – y[j]), với mọi i thuộc khoảng [1..n] và j thuộc [i+1 .. m] Kết quả = F[n,m] * Ghi chú: abs(x) là hàm cho giá trị tuyệt đối của biểu thức x trong Pascal. Ví dụ: File dữ liệu vào Robot.inp có cấu trúc nhƣ sau: 65 5 1 9 12 20 28 6 3 25 30 10 File dữ liệu ra Robot.out có cấu trúc nhƣ sau 11 Bảng phƣơng án F sau khi tính có kết quả nhƣ sau: 0 4 5 6 F 1 2 3 0 0 0 0 0 0 0 0 1 0 2 2 6 9 17 25 2 0 0 3 5 8 16 24 3 0 0 0 4 5 13 21 4 0 0 0 0 17 9 7 5 0 0 0 0 0 27 11 Hình 2.4 Kết quả bảng phương án F[n,m] bài “Robot” 12 Bài 2: Đoạn gối nhau dài nhất Cho N đoạn thẳng trên trục số với các điểm đầu ai và điểm cuối bi là những số nguyên trong khoảng 1000..1000, ai < bi. Hãy tìm số lƣợng tối đa K đoạn thẳng gối nhau liên tiếp. Hai đoạn thẳng [a,b] và [c,d] đƣợc gọi là gối nhau nếu xếp chúng trên cùng một trục số thì điểm đầu đoạn này trùng với điểm cuối của đoạn kia, tức là c = b hoặc d = a. Dữ liệu vào: tệp văn bản DOAN.INP gồm - Dòng đầu số N cho biết tổng các đoạn - N dòng tiếp theo , mỗi dòng cho biết 2 số nguyên là điểm đầu ai và điểm cuối bi. - Các số trên cùng một dòng cách nhau ít nhất một khoảng cách. Dữ liệu ra: tệp văn bản DOAN.OUT chứa: - Duy nhất một số nguyên cho biết số lƣợng tối đa các đoạn tìm đƣợc. Ví dụ: DOAN.INP DOAN.OUT 5 3 2 7 1 3 7 9 3 4 4 5 Ví dụ trên cho biết có tối đa 3 đoạn gối nhau liên tiếp là [1,3], [3,4] và [4,5]. 13 Thuật toán quy hoạch động nhƣ sau Để có thể quy hoạch động trƣớc tiên ta cần sắp xếp tăng dần các đoạn theo đầu phải của chúng. Sau đó tiến hành quy hoạch nhƣ sau:  Gọi L[i] là số lƣợng tối đa các đoạn gối nhau tính từ 1 đến i.  Ban đầu độ dài tối đa tại đoạn thứ i là 1 (vì chỉ có chính nó). Đây là bài toán cơ sở quy hoạch động.  Với mỗi đoạn thứ i, ta tìm tất cả các đoạn thứ j (j=1..i-1) mà có điểm cuối = điểm đầu của i và độ dài L[j] là lớn nhất. Nếu thỏa mãn thì ta thực hiện gán L[i]:=L[j]+1(độ dài của đoạn thứ i bằng độ dài của đoạn thứ j +1 (j đang là dài nhất)). 2.4. Quy hoạch động kết hợp xử lý Bit để mô tả trạng thái bài toán. 2.4.1 Bit và các thao tác xử lý Bit. 2.4.1.1 Quy ước về vị trí của các bit. 2.4.1.2 Các phép toán logic 2.4.1.3 Một số ứng dụng 2.4.2 Một số bài toán cùng lớp dùng quy hoạch động kết hợp bit. Dƣới đây là một số bài toán quy hoạch động kết hợp xử lý bit để mô tả trạng thái của bài toán. Bài 1: Chọn ô Cho một bảng hình chữ nhật kích thƣớc 4 × n ô vuông. Các dòng đƣợc đánh số từ 1 đến 4, từ trên xuống dƣới, các cột đƣợc đánh số từ 1 đến n từ trái qua phải. Ô nằm trên giao của dòng i và cột j đƣợc gọi là ô (i,j). Trên mỗi ô (i,j) có ghi một số nguyên aij , i = 1, 2, 3, 4; j = 1,2, …, n. Một cách chọn ô là việc xác định một tập con khác rỗng S của tập tất cả các ô của bảng sao cho không có hai ô nào trong S có chung cạnh. Các ô trong tập S đƣợc gọi là ô đƣợc chọn, tổng các số trong các ô đƣợc chọn đƣợc gọi là trọng lƣợng của cách chọn. 14 Ví dụ: Xét bảng với n=3, trong hình vẽ dƣới đây 1 2 3 1 -1 9 3 2 -4 5 -6 3 7 8 9 4 9 7 2 Cách chọn cần tìm là tập các ô S = {(3,1), (1,2), (4,2), (3,3)} với trọng lƣợng 32. Yêu cầu: Hãy tìm cách chọn ô với trọng lƣợng lớn nhất. Dữ liệu: Vào từ file van bản SELECT.INP:  Dòng đầu tiên chứa số nguyên dƣơng n là số cột của bảng.  Dòng thứ j trong số n dòng tiếp theo chứa 4 số nguyên a1j, a2j, a3j, a4j, hai số liên tiếp cách nhau ít nhất một dấu cách, là 4 số trên cột j của bảng. Kết quả: Ghi ra file văn bản SELECT.OUT trọng lƣợng của cách chọn tìm đƣợc. Hạn chế: Trong tất cả các test: n ≤ 10000; |aij|≤ 30000. Có 50% số lƣợng test với n ≤ 1000. Cách giải Mỗi cột có 4 dòng nên ta có thể dùng dãy nhị phân gồm 4 bit để biểu diễn. Tùy vào giá trị của bit thứ k của cột thứ i bằng 0 hoặc 1 cho biết dòng thứ k của cột thứ i có đƣợc chọn hay không?(0 <= k <= 3) Dãy nhị phân có 4 bit tƣơng ứng với 24 trạng thái, biểu diễn từ 0 tới 24 – 1. Gọi F[i,x] là tổng trọng lƣợng lớn nhất xét từ cột thứ 1 tới cột thứ i và trạng thái chọn của cột thứ i đƣợc biểu diễn bằng biến x. 15 Ta có công thức truy hồi nhƣ sau F[i,x]:=max(F[i-1,y])+sum(i,x) Trong đó: Biến x và y là 2 trạng thái tƣơng ứng của cột thứ i và i – 1 . Theo yêu cầu của bài toán thì trạng thái x và y phải thỏa mãn, bit thứ k của biến x phải khác bit thứ k của biến y vì việc chọn ô phải thỏa mãn không có hai ô nào có chung cạnh (Getbit(k,x) <> Getbit(k,y)) Hàm Sum(i,x) là trọng số của cột thứ i, tƣơng ứng với trạng thái x. Cài đặt: Biến A chứa giá trị của bảng, biến m = 24 – 1 , với m +1 là số trạng thái. Trong chƣơng trình sẽ sử dụng một số hàm nhƣ sau: + Lấy bit thứ k của trạng thái x: Getbit(k,x) function getbit(k,x:word):byte; begin getbit:=(x shr k)and 1; end; + Hàm kiểm tra trạng thái x có thỏa mãn yêu cầu bài toán hay không (không có hai ô nào có chung cạnh), nghĩa là bit thứ k và bit thứ k – 1 của trạng thái x phải khác nhau: function ok(x:word):boolean; begin ok:=false; for k:=1 to 3 do if (getbit(k-1,x)=1) and (getbit(k,x)=1) then exit; ok:=true; end; + Hàm kiểm tra trạng thái x và trạng thái y có thỏa mãn yêu cầu bài toán không (không có hai ô nào có chung cạnh), nghĩa là bit thứ k của trạng thái x và bit thứ k của trạng thái y phải khác nhau: function check(x,y:word):boolean; 16 begin check:=false; for k:=0 to 3 do if (getbit(k,x)=1) and (getbit(k,y)=1) then exit; check:=true; end; + Tính trọng lƣợng của cột thứ i ứng với trạng thái x: function sum(i,x:word):longint; var t := longint; begin t:=0; for k:=0 to 3 do if (getbit(k,x)=1) then t:=t+a[k+1,i]; sum:=t; end; Giải thích: Sau khi kiểm tra trạng thái của cột x (ok(x)), cột y (ok(y)), kiểm tra trạng thái của 2 cột x và y (check(x,y)). Dùng công thức truy hồi sau đây để tính: F[i,x]:=max(F[i-1,y])+sum(i,x) Để tính công thức trên ta sử dụng đoạn code sau đây: vc:=1000000000; for i:=1 to n do {xét lần lượt n cột} for x:=0 to 15 do {với mỗi cột xét 24 trạng thái} if ok(x) then {nếu trạng thái x thỏa mãn bài toán} begin max:=-vc; {Tìm trạng thái y của cột thứ i-1 có tổng trọng lượng lớn nhất} for y:=1 to 15 do if check(x,y) and ok(y) then if max trạng thái có 3 đỉnh đƣợc đi, và đỉnh kết thúc hành trình là đỉnh 5 (tính từ phải qua), với biểu diễn trong hệ thập phân tƣơng ứng của dãy này là 19.