Đường đi lớn nhất

Nguồn: CLUE OJ – Chương 20: Quay lui (MarisaOJ) Độ khó: Dễ Quay lui Quy hoạch động

Đề bài

Khu rừng có dạng một bảng $4 \times 4$. Ở mỗi ô $(i, j)$ Marisa có thể đến ô $(i + 1, j)$ hoặc $(i, j + 1)$.

Ô $(i, j)$ có $A_{i,j}$ cây nấm. Hành trình của Marisa bắt đầu từ $(1, 1)$ và kết thúc ở $(4, 4)$. Hỏi Marisa có thể hái được nhiều nhất bao nhiêu cây nấm?

Input: 4 dòng, mỗi dòng gồm 4 số nguyên.

Output: một số nguyên duy nhất là số cây nấm lớn nhất Marisa có thể hái.

Điều kiện: $1 \le A_{i,j} \le 10^9$.

Ví dụ – input

2 2 2 1
1 1 2 1
1 1 2 1
1 1 2 2

Ví dụ – output

14

Lời mở đầu

Đây là bài khởi động rất nhẹ nhàng của chương Quay lui. Bảng chỉ có $4 \times 4$ nên số đường đi rất ít, ta hoàn toàn có thể thử hết mọi đường đi bằng một hàm đệ quy: đứng ở mỗi ô thì có 2 lựa chọn "đi xuống" hoặc "sang phải", thử lần lượt từng lựa chọn rồi quay lui. Sau đó mình giới thiệu thêm cách quy hoạch động – cách mà các bạn sẽ dùng khi bảng to lên. Có một cái bẫy nhỏ về tràn số, các bạn để ý nhé.

Dành cho học viên · Ưu tiênNộp bài trên hệ thống CLUE OJ

Link này chỉ học viên đã tham gia tổ chức mới vào được. Học viên nên ưu tiên nộp ở đây vì sẽ được chấm nhanh hơn.

Nộp bài trên CLUE OJ

Lộ trình lời giải, bấm vào từng phần để nhảy tới:

Bộ test100 testÝ tưởng20 đường điCách 1Quay luiCách 2QHĐ

Bộ testBộ test chính thức có gì?

Số test	Kích thước bảng	$A_{i.j}$ nhỏ nhất	$A_{i.j}$ lớn nhất	Đáp án lớn nhất
100	luôn là $4 \times 4$	1	991.249.216	2.310.241.686

Bài không chia subtask: mọi test đều là bảng $4 \times 4$. Điều đáng chú ý duy nhất là độ lớn của số: mỗi ô tới gần $10^9$, một đường đi đi qua 7 ô nên tổng có thể tới $7 \cdot 10^9$, vượt xa giới hạn của int (khoảng $2{,}1 \cdot 10^9$). Trong bộ test có 1 test (test 087) có đáp án vượt int – bạn nào dùng int sẽ "rớt" đúng test này.

Cách	Ý tưởng	Kết quả chạy thật
Cách 1 (C++)	Quay lui thử cả 20 đường đi, dùng long long	100/100 test, chậm nhất 0,005 giây
Cách 1 nhưng dùng int	Giống hệt, chỉ đổi kiểu dữ liệu	99/100 test – sai test 087 vì tràn số
Cách 2 (C++)	Quy hoạch động $f[i][j]$	100/100 test, chậm nhất 0,003 giây
Python cả 2 cách	Viết thêm cho các bạn học Python	100/100 test, dưới 0,03 giây

Ý tưởngMỗi ô có 2 ngã rẽ – thử hết rồi quay lui

Từ $(1, 1)$ tới $(4, 4)$ Marisa luôn đi đúng 3 bước xuống và 3 bước sang phải, theo một thứ tự nào đó. Vậy số đường đi là số cách xếp 3 chữ X (xuống) và 3 chữ P (phải) thành một dãy 6 ký tự: $C_6^3 = 20$ đường. Quá ít! Ta cứ thử hết cả 20 đường, đường nào hái được nhiều nấm nhất thì lấy.

Để "thử hết" một cách có hệ thống, ta viết hàm đệ quy Try(i, j, s) nghĩa là "Marisa đang bước vào ô $(i, j)$, trước đó đã hái được $s$ cây nấm":

Hàm quay lui Try(i, j, s)

1. Hái nấm ở ô hiện tại: $s = s + A_{i,j}$.
2. Nếu đã tới đích $(4, 4)$ → so sánh $s$ với kết quả tốt nhất best, rồi quay về.
3. Nếu còn đi xuống được ($i < 4$) → thử Try(i + 1, j, s).
4. Nếu còn sang phải được ($j < 4$) → thử Try(i, j + 1, s).

Khi nhánh "đi xuống" chạy xong và trả về, máy tự động quay lui về đúng ô $(i, j)$ với đúng giá trị $s$ cũ (vì $s$ là tham số truyền theo giá trị, mỗi lời gọi có bản sao riêng) để thử tiếp nhánh "sang phải". Không cần "xoá" gì cả – đó là cái hay của việc truyền tham số.

Em sửa bảng rồi bấm Tiếp để xem máy lần lượt thử 20 đường đi. Ô viền cam là chỗ máy quay lui về để rẽ hướng khác so với đường trước:

Bảng 4×4 (16 số)

Ví dụ nhanh:

Cách 1Quay lui thử mọi đường đi

Đây chính là thuật toán ở trên viết thành code. Mảng a và biến best khai báo toàn cục để hàm Try dùng được.

C++▶ Chạy tay từng dòng codeCách 1: hàm Try(i, j, s) thử đi xuống rồi sang phải, quay lui khi tới đích.

Dữ liệu vào (stdin) – sửa thoải mái2 2 2 1 1 1 2 1 1 1 2 1 1 1 2 2

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

Khung bên phải vẽ ngăn xếp lời gọi: mỗi tầng là một ô trên đường đang đi. Khi một lời gọi kết thúc, tầng trên cùng bị bỏ đi – đó chính là bước quay lui.

1. s += a[i][j] sửa bản sao s của riêng lời gọi này, không ảnh hưởng lời gọi cha. Nhờ vậy khi nhánh "đi xuống" kết thúc, nhánh "sang phải" vẫn nhận đúng giá trị $s$ của ô $(i, j)$.
2. Hai lệnh if(i < 4), if(j < 4) giữ Marisa không đi ra ngoài bảng. Ở hàng 4 chỉ còn đường sang phải, ở cột 4 chỉ còn đường đi xuống.
3. Bắt buộc dùng long long cho a, s, best: mình đã thử đổi sang int và nộp lại, kết quả chỉ 99/100 – sai test 087 có đáp án 2.310.241.686 > $2^{31} - 1$.

Không gian$O(1)$ (bảng 4×4)

Thời gian$O(C_{2n-2}^{n-1})$ – với $n = 4$ là 20 đường, 69 lời gọi

Kết quả chạy thật: bản C++ đúng 100/100 test, chậm nhất 0,005 giây; bản Python cũng 100/100, chậm nhất 0,025 giây. Hàm Try chỉ được gọi 69 lần cho mỗi test (mỗi ô $(i, j)$ được gọi đúng bằng số đường đi từ $(1, 1)$ tới nó).

Cách 2Quy hoạch động – khi bảng to lên

Nếu bảng là $1000 \times 1000$ thì số đường đi là con số khổng lồ, quay lui không chạy nổi. Để ý: muốn tới ô $(i, j)$ thì bước cuối cùng phải đến từ ô trên $(i - 1, j)$ hoặc từ ô bên trái $(i, j - 1)$. Gọi $f[i][j]$ là số nấm nhiều nhất hái được khi đi từ $(1, 1)$ tới $(i, j)$, ta có:

Công thức

$f[i][j]$ $= \max(f[i-1][j],\ f[i][j-1])$ $+ A_{i,j}$, với hàng đầu và cột đầu chỉ có một hướng đến. Đáp án là $f[4][4]$.

Thay vì đi lại 20 đường, mỗi ô chỉ được tính đúng 1 lần.

C++▶ Chạy tay từng dòng codeCách 2: quy hoạch động, mỗi ô f[i][j] lấy max của ô trên và ô trái.

Dữ liệu vào (stdin) – sửa thoải mái2 2 2 1 1 1 2 1 1 1 2 1 1 1 2 2

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

Không gian$O(n^2)$

Thời gian$O(n^2)$ – 16 ô

Kết quả chạy thật: bản C++ đúng 100/100 test, chậm nhất 0,003 giây; bản Python 100/100, chậm nhất 0,03 giây.

Ghi chú của mình: cả 2 cách (C++ và Python) đều đạt 100/100 test trên CLUE OJ. Với bảng nhỏ $4 \times 4$ quay lui là đủ và rất dễ nghĩ; cách quy hoạch động là "phiên bản nâng cấp" để chuẩn bị cho các bài lưới lớn. Nhớ dùng long long – bản dùng int chỉ được 99/100.

Rất vui khi anh em nào đã đọc đến những dòng cuối cùng này. Anh em đọc chắc cũng mỏi mắt luôn chứ 😅 vậy anh em nghĩ người viết ra hết đống ở trên còn thế nào nữa 🤪. Vậy nên đừng tiếc gì cho mình một lời bình luận hoặc chia sẻ bài viết để động viên mình nè. Chúc anh em học tốt và gặt hái nhiều thành công 😇