Gói kẹo

Nguồn: CLUE OJ – Chương 22: Quy hoạch động Độ khó: Khá Quy hoạch động Nén giá trị

Đề bài

Đức có $N$ túi kẹo được xếp thành một đường thẳng $(1 \le N \le 5000)$, túi kẹo thứ $i$ có $A_i$ viên kẹo $(1 \le A_i \le 10^9;\ 1 \le i \le N)$. Anh ta muốn các túi kẹo phải được xếp thành một dãy sao cho túi kẹo bên phải có số kẹo lớn hơn hoặc bằng túi kẹo bên trái. Vì không muốn thay đổi thứ tự các gói kẹo nên Đức lấy ra hoặc thêm vào các túi kẹo một số kẹo nhất định. Vì cần có thời gian suy nghĩ nên mỗi lần Đức chỉ thực hiện một thao tác lấy ra khỏi túi 1 viên kẹo hoặc thêm 1 viên kẹo vào túi. Hỏi cần ít nhất bao nhiêu thao tác để Đức có thể thu được kết quả như mong muốn.

Input

• Dòng 1: chứa số nguyên $N$ là số túi kẹo của Đức.
• Dòng 2: chứa $N$ số nguyên, mỗi số cách nhau 1 kí tự trống, lần lượt là số kẹo $A_i$ của túi kẹo thứ $i$.

Output

• Chứa 1 số nguyên duy nhất là số lần thực hiện thao tác của Đức.

Subtask (dựa trên bộ test, trong đề thi gốc không có phần giới hạn này):

• Subtask 1: $n \le 20$.
• Subtask 2: $n \le 1000,\ a \le 10^5$.
• Subtask 3: giới hạn gốc.

Ví dụ 1 – input

3
4 3 6

Ví dụ 1 – output

1

Ví dụ 2 – input

5
2 3 1 5 4

Ví dụ 2 – output

3

Giải thích:

• Ví dụ 1: cách 1 – thêm vào gói 2 một viên kẹo (được $4, 4, 6$); cách 2 – lấy ra khỏi gói 1 một viên kẹo (được $3, 3, 6$). Đều mất 1 thao tác.
• Ví dụ 2: cách 1 – lấy ra từ gói 2 một viên kẹo, thêm vào gói 3 một viên kẹo, thêm vào gói 5 một viên kẹo (được $2, 2, 2, 5, 5$); cách 2 – thêm vào gói 3 hai viên kẹo, thêm vào gói 5 một viên kẹo (được $2, 3, 3, 5, 5$). Đều mất 3 thao tác.

Lời mở đầu

Phát biểu gọn lại: cho dãy $A$, tìm dãy không giảm $B$ sao cho tổng $\sum |A_i - B_i|$ nhỏ nhất (mỗi viên kẹo thêm/bớt là 1 thao tác). Đây là bài quy hoạch động rất kinh điển. Mình sẽ đi theo đúng 3 subtask: QHĐ theo giá trị của túi cuối (bảng đầy đủ) → bỏ bớt bộ nhớ chỉ giữ 1 hàng → dùng một nhận xét quan trọng để nén giá trị và ăn trọn 100% điểm.

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ộ test3 subtaskÝ tưởngdp[i][v]Cách 1Bảng 36%Cách 21 hàng 60%Cách 3Nén 100%

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

Test	$n$	$A_i$ lớn nhất	Số giá trị khác nhau (nhiều nhất)	Đáp án lớn nhất
1–30	1–20	20	14	88
31–60	135–979	99.934	661	12.684.925
61–100	5000–5.000	999.986.234	3.861	363.524.737.181

Bộ test khớp đúng 3 subtask của đề. Trong subtask 1 không chỉ $n \le 20$ mà các số kẹo cũng chỉ tới $20$. Ở subtask 3, đáp án lên tới khoảng $3{,}6 \cdot 10^{11}$ – phải dùng long long. Có vài test $n = 1$ (đáp án $0$, dãy 1 phần tử luôn không giảm).

Subtask	Điều kiện	Test	Cách 1 (bảng đầy đủ)	Cách 2 (1 hàng)	Cách 3 (nén giá trị)
1	$n \le 20$	1–30	qua	qua	qua
2	$n \le 1000,\ a \le 10^5$	31–60	6/30 test, còn lại tràn bộ nhớ	qua	qua
3	$n \le 5000,\ a \le 10^9$	61–100	tràn bộ nhớ	tràn bộ nhớ	qua

Ý tưởngTrạng thái QHĐ: túi cuối cùng có bao nhiêu viên?

Khi xếp từ trái sang phải, điều duy nhất ràng buộc túi $i$ là số kẹo của túi $i-1$ sau khi sửa (túi $i$ phải lớn hơn hoặc bằng). Vì vậy trạng thái tự nhiên là:

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

$dp[i][v]$ = số thao tác ít nhất để sửa $i$ túi đầu thành dãy không giảm, trong đó túi $i$ có đúng $v$ viên. $$dp[i][v] = |A_i - v| + \min_{u \le v} dp[i-1][u], \qquad dp[0][v] = 0.$$ Đáp án là $\min_v dp[n][v]$.

Phần $\min_{u \le v} dp[i-1][u]$ là min tiền tố của hàng trước: khi duyệt $v$ tăng dần ta chỉ cần giữ một biến mn và cập nhật mn = min(mn, dp[i-1][v]), nên mỗi ô tính trong $O(1)$.

Câu hỏi còn lại: $v$ chạy trong khoảng nào? Đây là chỗ quyết định độ phức tạp:

Nhận xét quan trọng (nén giá trị)

Luôn có một cách sửa tối ưu mà số kẹo cuối cùng của mỗi túi đều bằng một trong các giá trị $A_1, A_2, \ldots, A_n$ ban đầu.

Vì sao? Xét một cách sửa tối ưu và một khối các túi liền nhau cùng nhận chung giá trị $t$, trong khi $t$ không trùng giá trị $A$ nào. Nếu dời cả khối lên $t + 1$ thì mỗi túi có $A_i > t$ bớt 1 thao tác, mỗi túi có $A_i < t$ thêm 1 thao tác; dời xuống $t - 1$ thì ngược lại. Hai thay đổi này trái dấu nhau, nên luôn có một chiều không làm tăng tổng. Cứ dời theo chiều đó cho tới khi $t$ chạm một giá trị $A_i$ (hoặc chạm khối bên cạnh – khi đó gộp 2 khối lại và làm tiếp). Cuối cùng mọi khối đều mang giá trị nằm trong tập $A$. Nhờ vậy $v$ chỉ cần chạy qua các giá trị khác nhau của $A$ (tối đa $n$ giá trị) thay vì từ $1$ đến $10^9$.

Em nhập dãy rồi bấm Tiếp để xem bảng $dp$ được điền dần. Các cột là các giá trị khác nhau của $A$ (đã sắp tăng). Ô vàng là ô đang tính; các ô xanh tím ở hàng trên là đoạn tiền tố mà nó lấy min, ô viền đậm là ô đạt min. Bước cuối mình lần ngược để chỉ ra dãy kẹo sau khi sửa:

ô đang tínhtiền tố hàng trênô đạt minđường lần ngược

Số kẹo A

Ví dụ nhanh:

Cách 1Bảng đầy đủ dp[i][v], v từ 1 đến max A (subtask 1)

Chưa dùng nhận xét nén giá trị: cho $v$ chạy từ $1$ tới $V = \max A_i$ (rõ ràng không bao giờ cần nhiều kẹo hơn túi lớn nhất, cũng không cần ít hơn 1). Bảng có $(n+1) \times (V+1)$ ô.

C++▶ Chạy tay từng dòng codeCách 1: bảng dp[i][v] đầy đủ, v chạy từ 1 đến max A.

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

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

Để bảng vừa màn hình, khung này nhận n ≤ 4 và số kẹo ≤ 6.

1. mn khởi tạo bằng LLONG_MAX ở đầu mỗi hàng, rồi "nuốt" dần dp[i-1][1], dp[i-1][2], … nên tại cột $v$ nó đúng bằng $\min_{u \le v} dp[i-1][u]$.
2. Hàng $0$ toàn số $0$ (vector khởi tạo sẵn bằng 0): chưa có túi nào thì chưa tốn thao tác nào.

Không gian$O(n \cdot V)$

Thời gian$O(n \cdot V)$

Kết quả chạy thật (mình giới hạn bộ nhớ 256 MB đúng như đề): đúng 36/100 test. Cả 30 test subtask 1 qua ngay (bảng chỉ cỡ $21 \times 21$). Ở subtask 2, bảng $1001 \times 100\,001$ số long long tốn tới khoảng 800 MB – chỉ 6/30 test có $V$ đủ nhỏ để lọt dưới 256 MB, 24 test còn lại tràn bộ nhớ (khi chạy không giới hạn bộ nhớ thì các test này cho kết quả đúng, chậm nhất 0,59 giây – chứng tỏ công thức đúng, chỉ là quá tốn bộ nhớ). Subtask 3 với $V = 10^9$ thì đến một hàng của bảng cũng không cấp phát nổi.

Cách 2Chỉ giữ 1 hàng (subtask 1, 2)

Hàng $i$ chỉ dùng tới hàng $i - 1$, nên chỉ cần một mảng dp[v] và ghi đè lên chính nó. Mẹo nằm ở thứ tự: khi duyệt $v$ tăng dần, ngay trước khi ghi đè dp[v] thì nó vẫn là giá trị của hàng cũ – ta nạp nó vào mn trước, rồi mới ghi giá trị mới. Các ô $u < v$ đã bị ghi đè cũng không sao, vì giá trị cũ của chúng đã nằm sẵn trong mn.

C++▶ Chạy tay từng dòng codeCách 2: chỉ giữ 1 hàng dp[v], ghi đè từ trái sang phải.

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

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

Quan sát ranh giới giữa phần xanh lá (đã là hàng mới) và phần còn lại (vẫn là hàng cũ).

Không gian$O(V)$

Thời gian$O(n \cdot V)$

Kết quả chạy thật: đúng 60/100 test (trọn subtask 1 và 2), chậm nhất 0,11 giây, bộ nhớ chỉ khoảng 1 MB. 40 test subtask 3 vẫn tràn bộ nhớ: một hàng $10^9$ số long long đã là 8 GB, chưa kể $5000 \cdot 10^9$ phép tính. Bản Python của cách này chỉ được 30/100: vòng lặp $n \cdot V \approx 10^8$ bước quá chậm với Python.

Cách 3Nén giá trị – O(n²) (full điểm)

Áp dụng nhận xét ở phần ý tưởng: lấy mảng b gồm các giá trị khác nhau của $A$ sắp tăng dần ($m \le n$ phần tử), cho trạng thái chạy trên chỉ số $j$ của b thay vì trên chính giá trị. Công thức giữ nguyên, chỉ thay $v$ bằng $b_j$:

$$dp[i][j] = |A_i - b_j| + \min_{k \le j} dp[i-1][k].$$

C++▶ Chạy tay từng dòng codeCách 3: nén giá trị – cột chỉ là các giá trị khác nhau của A, O(n²).

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

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

1. sort + unique + erase là bộ 3 quen thuộc để lấy các giá trị khác nhau đã sắp xếp.
2. Vì $b$ tăng dần nên "$k \le j$" đúng nghĩa là "túi trước có số kẹo $\le$ túi hiện tại" – ràng buộc không giảm vẫn được giữ.
3. Với $n = 5000$: khoảng $n \cdot m \le 2{,}5 \cdot 10^7$ phép tính, bộ nhớ chỉ $O(n)$.

Không gian$O(n)$

Thời gian$O(n^2)$ (cộng $O(n \log n)$ để sắp xếp)

Kết quả chạy thật: đúng 100/100 test, test chậm nhất ($n = 5000$) chỉ mất 0,032 giây. Bản Python cùng ý tưởng đúng 60/100, 40 test $n = 5000$ mất khoảng 1,8–2,2 giây nên quá 1 giây; bản Python dùng hàng đợi ưu tiên (giới thiệu ngay dưới) thì đúng 100/100, chậm nhất 0,025 giây.

Mẹo nâng cao cho bản Python – hàng đợi ưu tiên $O(n \log n)$: duyệt lần lượt từng túi, đẩy $A_i$ vào một max-heap. Nếu phần tử lớn nhất trong heap $top > A_i$ thì cộng $top - A_i$ vào đáp án, rút $top$ ra và đẩy thêm một bản $A_i$ nữa. Hiểu nôm na: túi lớn nhất phía trước "vượt" túi hiện tại $top - A_i$ viên, ta phải tốn đúng chừng đó thao tác để san hai túi về cùng một mức nằm giữa $[A_i, top]$; heap lưu các "điểm gãy" của hàm chi phí $dp[i][\cdot]$ (đây là kỹ thuật slope trick, chứng minh chặt chẽ khá dài nên mình chỉ giới thiệu). Tab Python – hàng đợi ưu tiên ở khối code trên là cài đặt của mẹo này.

Ghi chú của mình: C++ – cách 1 (bảng đầy đủ) 36/100 do tràn bộ nhớ, cách 2 (1 hàng) 60/100, cách 3 (nén giá trị) 100/100 chậm nhất 0,032 giây. Python – cách 2: 30/100, cách 3: 60/100 (quá thời gian ở $n = 5000$), hàng đợi ưu tiên: 100/100. Mình chấm thử với giới hạn bộ nhớ 256 MB đúng như đề. Nhớ dùng long long vì đáp án tới khoảng $3{,}6 \cdot 10^{11}$.

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 😇