Nhảy lò cò (QHĐ, hàng đợi 2 đầu)
Đề bài
Nhảy lò cò là trò chơi dân gian khá quen thuộc đối với các bạn học sinh Việt Nam. Trong nội dung giao lưu giữa các đội tuyển thi HSG cấp tỉnh năm nay, ban tổ chức tổ chức cuộc thi nhảy lò cò, người chơi sẽ nhảy qua $N$ ô vuông liên tiếp được đánh số từ 1 đến $N$, mỗi ô ghi sẵn một số điểm trừ (chú ý: điểm trừ có thể âm). Do giỏi về thuật toán, Tí đã nhanh trí sử dụng máy tính để tính được số điểm trừ tối thiểu của mình. Tí có sức bật nhảy tối đa được $K$ ô liên tiếp (ví dụ: từ ô $i$ có thể nhảy đến ô $i + K$). Hỏi tổng số điểm tối thiểu bị trừ của Tí là bao nhiêu khi Tí cần nhảy từ ô ở vị trí 0 đến ô vị trí $N + 1$, hai ô này có điểm trừ bằng 0.
Dữ liệu vào:
- Dòng đầu ghi 2 số $N$ và $K$ $(5 \le N, K \le 5 \cdot 10^5)$.
- Dòng tiếp theo ghi $N$ số $a_1, a_2, \ldots, a_N$ $(|a_i| \le 10^4)$.
Kết quả ra: ghi ra một số duy nhất là tổng số điểm bị trừ nhỏ nhất của Tí.
Ràng buộc:
- Có 40% test tương ứng 40% số điểm của bài với $N, K \le 5 \cdot 10^2$.
- Có 30% test tương ứng 30% số điểm của bài với $N, K \le 5 \cdot 10^3$.
- Có 30% test tương ứng 30% số điểm của bài với $N, K \le 5 \cdot 10^5$.
7 3
20 30 40 25 15 20 2845Giải thích ví dụ: Tí nhảy các ô theo thứ tự $0 \to 2 \to 5 \to 8$ (mỗi bước nhảy không quá $K = 3$ ô). Điểm trừ là $a_2 + a_5 = 30 + 15 = 45$.
Lời mở đầu
Bài này là ví dụ rất đẹp cho thấy quy hoạch động thường có 2 tầng tối ưu: tầng 1 là nghĩ ra công thức (từ vét cạn mũ lên đa thức $O(NK)$), tầng 2 là tăng tốc chính công thức đó. Ở đây công thức cần "min của $K$ ô liền trước" – một bài toán cửa sổ trượt mà ta giải trong $O(1)$ trung bình bằng hàng đợi 2 đầu (deque). Mình đi đủ 3 bước, mỗi bước đều nộp thử trên bộ test thật để các bạn thấy mỗi cách ă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 OJLộ 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 | $N$ | $K$ | $a_i$ | Đáp án |
|---|---|---|---|---|
| 001–020 | 5 – 10 | 5 – 18 | -10 → 10 | -16 → 10 |
| 021–040 | 39 – 464 | 9 – 410 | -9.937 → 10.000 | -482.170 → 5.923 |
| 041–070 | 657 – 4.881 | 261 – 2.851 | -9.987 → 10.000 | -3.640.773 → 293 |
| 071–090 | 5.108 – 37.125 | 402 – 31.908 | -10.000 → 10.000 | -30.026.708 → 489 |
| 091–100 | 500.000 – 500.000 | 1 – 29.512 | 0 → 10.000 | 1 → 5.000.000.000 |
Đề chia 3 subtask và bộ test khớp đúng: test 001–040 có $N, K \le 500$, test 041–070 có $N, K \le 5000$, test 071–100 lớn (10 test cuối $N = 5 \cdot 10^5$). Vài điều đáng để ý:
- Có điểm trừ âm (9 test): lúc đó Tí "muốn" nhảy vào ô âm để được cộng điểm, đáp án có thể âm rất sâu (tới $-3 \cdot 10^7$).
- $K$ có thể lớn hơn $N$ (10 test): Tí nhảy thẳng từ ô 0 sang ô $N+1$, đáp án là 0.
- Test 100: $N = 5 \cdot 10^5$, $K = 1$, mọi ô đều 10000 – Tí buộc phải giẫm lên tất cả, đáp án $5 \cdot 10^9$ vượt
int. Phải dùnglong long.
| Subtask | Điều kiện | Test | Cách 1 vét cạn | Cách 2 QHĐ $O(NK)$ | Cách 3 QHĐ + deque |
|---|---|---|---|---|---|
| 1 (40%) | $N, K \le 500$ | 001–040 | 20/40 test | qua | qua |
| 2 (30%) | $N, K \le 5000$ | 041–070 | quá thời gian | qua | qua |
| 3 (30%) | $N, K \le 5 \cdot 10^5$ | 071–100 | quá thời gian | 24/30 test | qua |
Ý tưởngf[i] = a[i] + min của K ô liền trước
Gọi $f[i]$ là tổng điểm trừ nhỏ nhất để Tí đứng được ở ô $i$ (tính cả $a_i$). Bước nhảy cuối cùng tới ô $i$ phải xuất phát từ một ô $j$ trong khoảng $[i - K,\ i - 1]$ (và $j \ge 0$). Vậy:
Tính thẳng thì mỗi ô tốn $K$ phép so sánh → $O(NK)$, tới $2{,}5 \cdot 10^{11}$ khi $N = K = 5 \cdot 10^5$ – quá chậm. Nhưng để ý: "cửa sổ" $[i-K, i-1]$ chỉ trượt sang phải 1 ô mỗi lần. Ta giữ một deque chứa các chỉ số $j$ trong cửa sổ, sao cho $f[j]$ tăng dần từ đầu tới cuối:
- Đầu deque ra khỏi cửa sổ ($j < i - K$) → bỏ ở đầu. Lúc này đầu deque chính là min.
- Tính xong $f[i]$, trước khi đẩy $i$ vào cuối, bỏ ở cuối mọi $j$ có $f[j] \ge f[i]$: chúng vừa già hơn vừa không nhỏ hơn $i$, sẽ không bao giờ là min nữa.
Mỗi chỉ số vào deque 1 lần, ra tối đa 1 lần nên tổng chi phí chỉ $O(N)$. Em nhập dữ liệu rồi bấm Tiếp để xem cửa sổ (viền cam) trượt và deque thay đổi:
Cách 1Vét cạn: thử mọi cách nhảy
Hàm Try(i, sum): Tí đang ở ô $i$, đã bị trừ sum điểm. Nếu $i = N + 1$ thì cập nhật đáp án; ngược lại thử nhảy $d = 1, 2, \ldots, K$ ô (không vượt quá ô $N + 1$).
Kết quả chạy thật: đúng 20/100 test – quá thời gian test 021–100. Số cách nhảy tăng theo cấp số nhân ($K = 2$ đã là dãy Fibonacci), nên chỉ những test rất nhỏ mới chạy kịp.
Cách 2Quy hoạch động O(N·K)
Vét cạn chậm vì "đường tốt nhất tới ô $i$" bị tính đi tính lại theo mọi cách đã nhảy tới đó. Quy hoạch động lưu lại $f[i]$ và tính đúng một lần cho mỗi ô, theo công thức ở phần ý tưởng.
- Cận dưới
max(0, i - k)để không lùi quá ô 0 (khi $K > i$, kể cả trường hợp $K > N$). - Khởi tạo
f[i] = LLONG_MAXrồi lấy min, cuối cùng mới cộnga[i]– tránh cộng vàoLLONG_MAXgây tràn số.
Kết quả chạy thật: đúng 94/100 test – quá thời gian test 092–095, 097, 099. Ăn trọn subtask 1, 2 và cả những test lớn mà $N \cdot K$ nhỏ; chỉ trượt các test mà $N \cdot K$ lên tới hàng tỷ.
Cách 3Quy hoạch động + hàng đợi 2 đầu O(N)
Giữ nguyên công thức, chỉ thay vòng for j tìm min bằng deque như phần ý tưởng.
- Thứ tự trong vòng lặp rất quan trọng: bỏ đầu hết hạn → lấy min ở đầu → tính f[i] → bỏ cuối lớn hơn → đẩy i. Đẩy $i$ trước khi tính $f[i]$ là sai.
- Deque không bao giờ rỗng khi lấy
dq.front(): chỉ số $i - 1$ vừa được đẩy vào ở lượt trước và luôn còn trong cửa sổ. - So sánh
>=(không phải>) khi bỏ ở cuối: phần tử cũ bằng nhau cũng vô dụng vì nó hết hạn sớm hơn.
Kết quả chạy thật: đúng 100/100 test, chậm nhất 0,043 giây.
Bản Python (mình viết thêm, chấm trên cùng bộ test): cách 1 được 20/48 test – quá thời gian test 021–045, 071–073 (mình chỉ chạy thử test 001–045, 071–073 vì các test lớn hơn chắc chắn quá thời gian); cách 2 được 83/100 test – quá thời gian test 072, 075, 080–084, 088, 091–099; cách 3 được 100/100 test, chậm nhất 0,435 giây.
long long (test 100 đáp án $5 \cdot 10^9$) và đừng quên điểm trừ có thể âm, $K$ có thể lớn hơn $N$.
Nhận xét
Đăng nhận xét