Bán tượng

Nguồn: CLUE OJ – Chương 22: Quy hoạch động (STATUES) Độ khó: Trung bình Quy hoạch động QHĐ đoạn

Đề bài

Bờm phát hiện một hang ngầm chứa $N$ bức tượng cổ. Các bức tượng cổ khá lớn nên chỉ có thể lấy ra lần lượt từ hai cửa hang ngầm ở hai đầu. Theo đánh giá của các chuyên gia, bức tượng thứ $i$ từ trái sang có giá trị $v_i$.

Bờm rao bán $N$ bức tượng theo quy cách: mỗi lần bán một bức tượng (lấy ra từ một trong hai đầu của hang ngầm), bức tượng thứ $i$ nếu bán ở lượt thứ $j$ sẽ có giá $v_i \times j$.

Hãy xác định tổng thu lớn nhất nếu Bờm bán $N$ bức tượng theo cách tối ưu.

Dữ liệu:

• Dòng 1: số nguyên $N$ $(1 \le N \le 2000)$.
• Dòng $2 \ldots N + 1$: $N$ số nguyên $v_1, v_2, \ldots, v_N$ $(1 \le v_i \le 1000)$, mỗi số một dòng.

Kết quả: một số nguyên là tổng thu lớn nhất.

Subtask: 30% số test đầu tiên có $N \le 10$; 20% số test tiếp theo có $10 < N \le 24$; 50% số test còn lại có $24 < N \le 2000$.

Ví dụ – input

5
1
3
1
5
2

Ví dụ – output

43

Giải thích ví dụ: một cách tối ưu là bán theo thứ tự $v_1, v_5, v_2, v_3, v_4$ (trái, phải, trái, trái, còn lại): $1 \cdot 1 + 2 \cdot 2 + 3 \cdot 3 + 1 \cdot 4 + 5 \cdot 5$ $= 43$.

Lời mở đầu

Bài này là phiên bản tiếng Việt của bài kinh điển Treats for the Cows (USACO) – một bài nhập môn tuyệt vời cho quy hoạch động trên đoạn. Mình sẽ đi từng bước: vét cạn bằng bitmask, rồi đệ quy, rồi nhận ra đệ quy bị tính lặp → đệ quy có nhớ, cuối cùng chuyển thành bảng QHĐ điền theo độ dài đoạn. Mỗi cách mình đều chạy thật trên bộ test để các bạn thấy nó ăn được subtask nào.

Link nộp bài

Bấm vào nút bên dưới để nộp bài và được hệ thống CLUE OJ chấm tự động.

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ộ test3 subtaskÝ tưởngĐoạn [l, r]Cách 1BitmaskCách 2Đệ quyCách 3Có nhớCách 4QHĐ bảng

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

Test	Số test	$N$	$v_i$	Đáp án lớn nhất
1–30	30	5 – 10	1 – 999	29.427
31–40	10	11 – 15	1 – 994	40.294
41–50	10	24	1 – 991	101.992
51–100	50	2000	1 – 999	456.882.118

Kiểm tra trên bộ test thật: đúng như đề ghi, 30 test đầu có $N \le 10$, 20 test tiếp có $10 < N \le 24$ (10 test $N$ từ 11 đến 15, 10 test $N = 24$), 50 test cuối đều có $N = 2000$ – lớn nhất có thể. Đáp án lên tới hơn $4{,}5 \cdot 10^8$, còn trường hợp xấu nhất là $1000 \cdot (1 + 2 + \dots + 2000)$ $\approx 2 \cdot 10^9$ vượt kiểu int, nên mình dùng long long cho chắc.

Subtask	Điều kiện	Test	Cách 1 bitmask	Cách 2 đệ quy	Cách 3 đệ quy có nhớ	Cách 4 QHĐ bảng
1	$N \le 10$	1–30	qua	qua	qua	qua
2	$10 < N \le 24$	31–50	qua 10/20	qua	qua	qua
3	$N \le 2000$	51–100	quá thời gian	quá thời gian	qua	qua

Ý tưởngNhững bức tượng còn lại luôn là một đoạn liên tiếp

Tham lam "bán bức rẻ hơn trước" là SAI

Ý tưởng tự nhiên: bức nào rẻ thì bán sớm (nhân hệ số nhỏ), để bức đắt về sau. Nhưng thử với $v = (3, 5, 1, 4)$: tham lam so 2 đầu, chọn bán $3, 4, 1, 5$ được $3 \cdot 1 + 4 \cdot 2 + 1 \cdot 3 + 5 \cdot 4 = 34$; trong khi bán $4, 1, 3, 5$ thì được $4 + 2 + 9 + 20 = 35$. Tham lam chỉ nhìn 2 đầu nên không thấy được bức $1$ "nằm sâu" bên trong cần được lôi ra sớm.

Quan sát quan trọng: vì chỉ lấy từ 2 đầu nên các bức tượng còn lại luôn là một đoạn liên tiếp $[l, r]$. Đã bán $N - (r - l + 1)$ bức nên lượt hiện tại là $j = N - (r - l)$. Gọi

Trạng thái và công thức

$f[l][r]$ = tổng thu lớn nhất khi bán hết đoạn $[l, r]$ còn lại (bắt đầu từ lượt $j = N - (r - l)$). $$f[l][r] = \max\big(v_l \cdot j + f[l+1][r],\ \ v_r \cdot j + f[l][r-1]\big), \qquad f[l][l-1] = 0$$ Đáp án là $f[1][N]$.

Mỗi ô $f[l][r]$ chỉ cần 2 ô của đoạn ngắn hơn 1, nên ta điền bảng theo độ dài tăng dần: độ dài 1 (đường chéo), độ dài 2, ..., độ dài $N$ (ô góc trên bên phải). Em nhập dãy giá trị rồi bấm Tiếp để xem bảng được điền. Ô vàng đang tính, ô tím là $f[l+1][r]$ (bán bên trái), ô cam là $f[l][r-1]$ (bán bên phải):

Giá trị v

Ví dụ nhanh:

Cách 1Vét cạn thứ tự bán bằng bitmask – O(2ᴺ·N)

Ở mỗi lượt chỉ có 2 lựa chọn: bán đầu trái hay đầu phải. Vậy một cách bán ứng với một dãy $N$ bit (bit $j-1$ bằng 0 là lượt $j$ lấy bên trái, bằng 1 là lấy bên phải). Ta thử hết $2^N$ dãy bit, mỗi dãy mô phỏng lại $N$ lượt bán và lấy tổng lớn nhất. (Lượt cuối cùng chỉ còn 1 bức nên bit cuối không quan trọng – có trùng lặp, nhưng không sao.)

C++▶ Chạy tay từng dòng codeCách 1: mỗi mask là 1 thứ tự bán (bit = 1: bán bên phải).

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

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

Test đề có N = 5 (32 mask) khá dài nên khung này giới hạn N ≤ 4.

Không gian$O(N)$

Thời gian$O(2^N \cdot N)$

Kết quả chạy thật: đúng 40/100 test – qua subtask 1 và 10 test đầu của subtask 2 ($N \le 15$). Với $N = 24$: $2^{24} \cdot 24 \approx 4 \cdot 10^8$ phép tính, chạy khoảng 1,2 giây → quá thời gian sát nút. Còn 50 test $N = 2000$ thì in ra kết quả sai: 1 << n với $n \ge 31$ bị tràn kiểu int nên vòng lặp mask chạy sai hẳn (mà kể cả không tràn thì $2^{2000}$ cách bán cũng không bao giờ duyệt xong).

Cách 2Đệ quy thử 2 đầu – O(2ᴺ)

Viết lại vét cạn bằng đệ quy: hàm Try(l, r, j) trả về tổng thu lớn nhất khi còn đoạn $[l, r]$ và đang ở lượt $j$. Nó thử bán $v_l$ hoặc $v_r$ rồi gọi đệ quy cho phần còn lại. Không phải cộng lại từ đầu cho mỗi cách bán nên nhanh hơn cách 1 khoảng $N$ lần.

C++▶ Chạy tay từng dòng codeCách 2: Try(l, r, j) thử bán đầu trái hoặc đầu phải.

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

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

Khung bên phải là ngăn xếp lời gọi, mỗi tầng ghi đoạn còn lại và kết quả 2 nhánh đã tính.

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

Thời gian$O(2^N)$

Kết quả chạy thật: đúng 50/100 test – qua cả subtask 1 và 2 (test $N = 24$ chỉ khoảng 0,06 giây). Subtask 3 ($N = 2000$) thì $2^{2000}$ lời gọi, không bao giờ xong.

Cách 3Đệ quy có nhớ – O(N²)

Nhìn vào cây đệ quy của cách 2: từ $[1, N]$ đi "trái rồi phải" hay "phải rồi trái" đều về cùng đoạn $[2, N-1]$. Có rất nhiều lời gọi trùng nhau! Thực ra chỉ có khoảng $\frac{N^2}{2}$ đoạn $[l, r]$ khác nhau, và lượt $j = N - (r - l)$ được suy ra từ $l, r$ nên không cần là tham số. Vậy ta lưu kết quả mỗi đoạn vào memo[l][r], lần sau gặp lại thì trả về ngay.

C++▶ Chạy tay từng dòng codeCách 3: đệ quy có nhớ – mỗi đoạn [l, r] chỉ tính 1 lần.

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

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

Bảng bên trái là mảng memo: ô xanh nháy lên khi một lời gọi lấy lại kết quả đã lưu.

1. memset(memo, -1, sizeof memo): đánh dấu mọi ô "chưa tính" (giá trị thật luôn $\ge 0$ nên $-1$ không bị nhầm).
2. Câu return memo[l][r] = max(...) vừa lưu vừa trả về.
3. Độ sâu đệ quy tối đa $N + 1 = 2001$ tầng – an toàn với ngăn xếp mặc định.

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

Thời gian$O(N^2)$

Kết quả chạy thật: đúng 100/100 test, chậm nhất 0,05 giây. Đã full điểm! Mảng memo $2005 \times 2005$ số long long tốn khoảng 32 MB, trong giới hạn 256 MB.

Cách 4QHĐ bảng điền theo độ dài đoạn – O(N²)

Đệ quy có nhớ tính ô nào cần tới ô đó. Ta cũng có thể chủ động điền bảng từ dưới lên: đoạn độ dài len chỉ cần đoạn độ dài len - 1, nên vòng ngoài là len từ 1 đến $N$. Không có đệ quy nên chạy nhanh hơn và không lo tràn ngăn xếp.

C++▶ Chạy tay từng dòng codeCách 4: điền bảng f[l][r] theo độ dài đoạn tăng dần.

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

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

1. Với đoạn độ dài len, đã bán $N - len$ bức nên lượt hiện tại là j = n - len + 1.
2. Khi len = 1 thì f[l + 1][r] và f[l][r - 1] là đoạn rỗng – mảng toàn cục mặc định bằng 0, đúng bằng giá trị cần.
3. Bản Python mình chỉ giữ 1 hàng của bảng (các đoạn cùng độ dài) để tiết kiệm bộ nhớ: hàng mới chỉ cần hàng độ dài len - 1.

Không gian$O(N^2)$ (Python: $O(N)$)

Thời gian$O(N^2)$

Kết quả chạy thật: bản C++ đúng 100/100 test, chậm nhất 0,03 giây. Bản Python đúng 92/100 test: $2 \cdot 10^6$ phép tính với Python mất khoảng 0,8 – 1 giây nên vài test $N = 2000$ bị quá thời gian sát nút (1 giây).

Ghi chú của mình: Cách 1 (bitmask) 40/100, cách 2 (đệ quy) 50/100, cách 3 (đệ quy có nhớ) 100/100, cách 4 (QHĐ bảng) 100/100 với C++. Python dùng QHĐ bảng 1 hàng được 92/100 (chậm nhất 0,98 giây trong số test qua). Từ cách 2 sang cách 3 chỉ thêm đúng 3 dòng code mà từ "không bao giờ xong" thành 0,05 giây – đó là sức mạnh của việc nhớ lại kết quả bài toán con.

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 😇