Chọn số 3

Nguồn: CLUE OJ – Chương 22: Quy hoạch động Độ khó: Dễ Quy hoạch động 1 chiều Quay lui

Đề bài

Cho dãy số nguyên $a_1, a_2, \ldots, a_n$. Bạn được phép chọn bất kỳ số nào trong dãy số trên (hoặc không chọn số nào cả) nhưng không được chọn quá 2 số liên tiếp.

Yêu cầu: tìm cách chọn để tổng các số được chọn là lớn nhất.

Dữ liệu vào:

• Dòng đầu tiên ghi số nguyên dương $n$.
• Dòng thứ hai ghi $n$ số nguyên $a_1, a_2, \ldots, a_n$.

Kết quả: một số nguyên duy nhất là kết quả bài toán. Nếu không chọn số nào, kết quả bằng $0$.

Giới hạn:

• 40% số test tương ứng với 40% số điểm có $1 \le n \le 20$.
• 60% số test còn lại tương ứng với 60% số điểm có $1 \le n \le 10^5$.
• $|a_i| \le 10^6$.

Ví dụ – input

5
6 9 1 3 5

Ví dụ – output

23

Giải thích ví dụ: chọn $6, 9$ (2 số liên tiếp), bỏ số $1$, rồi chọn tiếp $3, 5$: tổng $6 + 9 + 3 + 5 = 23$. Không thể chọn cả 5 số vì sẽ có 3 số liên tiếp được chọn.

Lời mở đầu

Đây là bài khởi động rất đẹp của chương Quy hoạch động. Nó là "người anh em" của bài kinh điển không được chọn 2 số kề nhau, chỉ nới ra thành không quá 2 số liên tiếp. Mình sẽ đi từ cách vét cạn bằng quay lui (thử chọn / không chọn từng số) để ăn 40% điểm, rồi nhìn vào chính cây quay lui đó để rút ra công thức quy hoạch động $O(n)$ ăn trọn 100%.

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ộ test2 subtaskCách 1Quay lui 40%Ý tưởngBảng f[i]Cách 2QHĐ 100%

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

Test	$n$	Giá trị $a_i$	Tỉ lệ số âm	Đáp án
1–40	5–20	-20 … 20	33%	1 … 173
41–100	100000–100.000	-999.999 … 999.999	33%	6.560.601.712 … 6.827.932.030

Bộ test chia đúng như đề: 40 test đầu có $n \le 20$ (subtask 1), 60 test sau đều có $n = 100\,000$ (subtask 2). Khoảng 1/3 số trong dãy là số âm nên không thể "chọn hết". Đáp án của subtask 2 lên tới khoảng $6{,}8 \cdot 10^9$ – vượt quá kiểu int (tối đa khoảng $2{,}1 \cdot 10^9$), nên tổng phải lưu bằng long long.

Subtask	Điều kiện	Test	Cách 1 (quay lui)	Cách 2 (QHĐ)
1 (40%)	$n \le 20$	1–40	qua	qua
2 (60%)	$n \le 10^5$	41–100	quá thời gian	qua

Cách 1Quay lui: thử chọn / không chọn từng số (subtask 1)

Mỗi số chỉ có 2 khả năng: chọn hoặc không chọn. Ta đi lần lượt từ $a_1$ đến $a_n$ và nhớ thêm $k$ = số số liên tiếp vừa được chọn ngay trước:

Try(i, k, sum) – đang xét a[i], đã có k số liên tiếp được chọn ngay trước, tổng hiện tại là sum

• Nếu $i > n$: đã xét hết dãy, cập nhật best = max(best, sum).
• Không chọn $a_i$: chuỗi liên tiếp bị cắt, gọi Try(i + 1, 0, sum).
• Chọn $a_i$ – chỉ khi $k < 2$: gọi Try(i + 1, k + 1, sum + a[i]).

best khởi tạo bằng $0$ – ứng với cách "không chọn số nào", nên nếu mọi số đều âm thì đáp án tự động là $0$ đúng như đề yêu cầu.

C++▶ Chạy tay từng dòng codeCách 1: Try(i, k, sum) rẽ nhánh không chọn / chọn a[i], chỉ được chọn khi k < 2.

Dữ liệu vào (stdin) – sửa thoải mái4 5 -2 4 6

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

Bảng bên trái là dãy a (xanh: nhánh đang chọn, mờ: nhánh đang bỏ). Khung bên phải là ngăn xếp lời gọi.

Không gian$O(n)$ (độ sâu đệ quy)

Thời gian$O(2^n)$ – thực tế ít hơn vì nhánh "chọn" bị chặn khi $k = 2$

Kết quả chạy thật: bản C++ đúng 40/100 test – trọn subtask 1, test chậm nhất chỉ 0,005 giây. Cả 60 test của subtask 2 ($n = 10^5$) đều quá thời gian: số nhánh tăng theo cấp số nhân, máy chạy tới lúc bị dừng vẫn chưa xong. Bản Python cũng qua 40 test đầu (chậm nhất 0,07 giây); với $n = 10^5$ thì Python còn báo lỗi vượt độ sâu đệ quy trước cả khi kịp quá thời gian.

Ý tưởng QHĐNhìn vào số cuối cùng

Gọi $f[i]$ là tổng lớn nhất khi chỉ được chọn trong $i$ số đầu $a_1, \ldots, a_i$ (vẫn tuân theo luật không quá 2 số liên tiếp). Đáp án là $f[n]$. Để tính $f[i]$, chỉ cần hỏi: cách chọn tốt nhất kết thúc như thế nào ở cuối? Chỉ có đúng 3 khả năng:

1. Không chọn $a_i$: phần còn lại là một cách chọn bất kỳ trong $i - 1$ số đầu → tốt nhất là $f[i-1]$.
2. Chọn $a_i$ nhưng không chọn $a_{i-1}$: $a_{i-1}$ là "vách ngăn", phía trước thoải mái → $f[i-2] + a_i$.
3. Chọn cả $a_{i-1}$ và $a_i$: khi đó bắt buộc không chọn $a_{i-2}$ (nếu không sẽ thành 3 số liên tiếp) → $f[i-3] + a_{i-1} + a_i$.

Công thức truy hồi

$$f[i] = \max\big(f[i-1],\ \ f[i-2] + a_i,\ \ f[i-3] + a_{i-1} + a_i\big)$$ với quy ước $f[0] = 0$ và $f$ của chỉ số âm cũng bằng $0$ (chưa có số nào). Khả năng 3 chỉ xét khi $i \ge 2$.

Vì sao đúng? Ba khả năng trên phủ hết mọi cách chọn hợp lệ (số cuối không chọn / chọn đơn lẻ / chọn thành cặp), và trong mỗi khả năng phần phía trước "vách ngăn" độc lập hoàn toàn với phần sau – nên lấy tốt nhất của phần trước ($f[\ldots]$) là tốt nhất. Mỗi $f[i]$ tính trong $O(1)$ → cả bài $O(n)$.

Em nhập dãy rồi bấm Tiếp để xem bảng $f$ được điền dần từng ô. Ô vàng là ô đang tính, các ô xanh tím là những ô nó dùng tới; bước cuối mình lần ngược để chỉ ra các số được chọn:

ô đang tínhô được dùng tớikhả năng tốt nhấtsố được chọn (bước cuối)

Dãy a

Ví dụ nhanh:

Cách 2Quy hoạch động $O(n)$ (full điểm)

Cài đặt đúng công thức trên với mảng f[0..n]. Để không phải xử lý chỉ số âm, mình viết điều kiện i >= 2, i >= 3 ngay trong biểu thức (chỉ số không hợp lệ thì coi như $0$).

C++▶ Chạy tay từng dòng codeCách 2: điền bảng f[0..n] theo công thức 3 khả năng, O(n).

Dữ liệu vào (stdin) – sửa thoải mái5 6 9 1 3 5

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

Ô vàng là f[i] đang tính, ô xanh tím là ô mà khả năng đang xét dùng tới.

1. Mảng a và f đều là long long: tổng có thể tới $10^5 \cdot 10^6 = 10^{11}$, vượt int. Trong bộ test thật đáp án lên tới khoảng $6{,}8 \cdot 10^9$, dùng int sẽ sai cả 60 test lớn.
2. $f[i] \ge f[i-1] \ge \ldots \ge f[0] = 0$, nên đáp án không bao giờ âm – trường hợp "không chọn gì" đã nằm sẵn trong công thức.
3. Dòng f[i] = f[i - 1] chạy trước, rồi hai dòng max lần lượt thử 2 khả năng còn lại.

Không gian$O(n)$

Thời gian$O(n)$

Kết quả chạy thật: đúng 100/100 test, test chậm nhất (n = 100 000) chỉ mất 0,015 giây. Bản Python cũng đúng 100/100, chậm nhất 0,08 giây.

Tối ưu thêm bộ nhớ (không bắt buộc): $f[i]$ chỉ dùng 3 giá trị ngay trước nên có thể chỉ giữ 3 biến f1 = f[i-1], f2 = f[i-2], f3 = f[i-3] và "trượt" chúng sau mỗi bước, bộ nhớ $O(1)$. Với $n = 10^5$ thì mảng cũng chỉ tốn chưa tới 2 MB, nên mình giữ mảng cho dễ đọc.

Ghi chú của mình: Cách 1 (quay lui) đạt 40/100 test – đúng phần 40% điểm của subtask 1; cách 2 (quy hoạch động $O(n)$) đạt 100/100, chậm nhất 0,015 giây (C++) và 0,08 giây (Python). Lỗi hay gặp nhất của bài này là dùng int cho tổng: 60 test lớn đều có đáp án vượt $2^{31}$.

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 😇