Bán tượng
Đề 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$.
5
1
3
1
5
243Giả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à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 OJBạn nào muốn thử nộp bài để hệ thống chấm xem có đúng hay không thì dùng link này nhé. Chưa có tài khoản thì tạo tài khoản rồi đăng nhập nộp bài thử hen.
Nộp bài trên CodeforcesLộ trình lời giải, bấm vào từng phần để nhảy tới:
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
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
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):
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.)
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.
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.
memo: ô xanh nháy lên khi một lời gọi lấy lại kết quả đã lưu.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).- Câu
return memo[l][r] = max(...)vừa lưu vừa trả về. - Độ sâu đệ quy tối đa $N + 1 = 2001$ tầng – an toàn với ngăn xếp mặc định.
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.
- 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. - Khi
len = 1thì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. - 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.
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).
Nhận xét
Đăng nhận xét