Chọn ĐTQG Tuyên Quang 2026 - Robot
Xem dạng PDFTrong trường hợp đề bài hiển thị không chính xác, bạn có thể tải đề bài tại đây: Đề bài
Một dây chuyền xuất khẩu cam của công ty XYZ tiến hành đánh giá sản phẩm. Trên dây chuyền có ~n~ quả cam đánh số từ ~1~ đến ~n~ đang được đưa vào đánh giá chất lượng, quả thứ ~i~ có hàm lượng độc tố là ~a_i~ ~(i = 1, 2, \dots, n)~. Rô bốt P của công ty thực hiện việc phân lô sản phẩm để chia ~n~ quả cam trên thành ~k~ lô. Cam được phân lô theo thứ tự từ đầu đến cuối, mỗi lô ít nhất một quả. Rô bốt Q của công ty đối tác thực hiện việc đánh giá chất lượng, với mỗi lô cam, rô bốt Q sẽ chọn ra một quả có hàm lượng độc tố lớn nhất để làm đại diện cho lô hàng đó.
Yêu cầu: Hãy lập trình giúp rô bốt P chia lô sao cho tổng hàm lượng độc tố của tất cả ~k~ lô cam là nhỏ nhất có thể.
Input
Dòng thứ nhất gồm hai số nguyên dương ~n, k~ ~(k \le n \le 2 \cdot 10^5)~;
Dòng thứ hai gồm ~n~ số nguyên dương ~a_1, a_2, \dots, a_n~ ~(a_i \le 10^9; 1 \le i \le n)~.
Các số ghi trên cùng một dòng được phân cách nhau bởi một dấu cách.
Output
Một số nguyên là tổng hàm lượng độc tố nhỏ nhất tìm được.
Scoring
| Subtask | Điểm | Ràng buộc |
|---|---|---|
| 1 | ~30\%~ | ~n \le 100~ |
| 2 | ~30\%~ | ~n \le 1000~ |
| 3 | ~20\%~ | ~a_i \le a_{i+1}~ ~(1 \le i < n)~ |
| 4 | ~20\%~ | Không có giới hạn gì thêm |
Sample Input 1
7 3
2 5 1 8 9 2 6
Sample Output 1
15
Notes
Các lô cam thỏa mãn:
Lô 1: ~2, 5~;
Lô 2: ~1~;
Lô 3: ~8, 9, 2, 6~.
Bình luận
1. Khi $k \cdot (n - k) \le 7 \times 10^7$: DP vs Monotonic Stack
Trạng thái: Đặt $m = n - k$. Gọi $dp[i]$ là tổng nhỏ nhất ở bước chia lô thứ $j$ khi xét $j + i$ quả đầu tiên ($0 \le i \le m$).
Tối ưu Stack: Để tính $nd[i]$, ta dùng công thức $nd[i] = \min(dp[p] + \max(a_x))$. Dùng Monotonic Stack lưu $a$ giảm dần ($d$), kèm giá trị $\min$ của $dp[p]$ của các đoạn bị gộp ($e$) và kết quả tối ưu tiền tố $\min(e + d)$ trên stack ($o$).
Độ phức tạp: $O(k \cdot (n - k))$.
2. Subtask cuối ($n \le 2 \times 10^5$, $k \cdot (n - k)$ lớn): WQS Binary Search vs Heuristic
Do hàm mục tiêu không lồi hoàn toàn, chặt nhị phân WQS có thể nhảy qua điểm $k$ (chỉ tìm được nghiệm chia $c1 < k$ và $c2 > k$ đoạn). Cách xử lý:
WQS (fa, fb): Nhân $a_i$ với $15120$ để tránh số thực, chặt nhị phân chi phí phạt $lo$ kết hợp Monotonic Stack trong $O(n \log(\max A))$. Nếu ra đúng $k$ đoạn thì xuất kết quả.
Truy vết và Khoanh vùng (fc, fd): Nếu lệch $k$, truy vết 2 phương án biên $c1 < k$ và $c2 > k$ để nội suy vị trí chia đoạn ước lượng tại mỗi chỉ số.
Sau đó chạy lại DP Monotonic Stack nhưng chỉ giới hạn trạng thái trong một dải băng hẹp bán kính $bw$ (khoảng $105$ đến $200$) quanh đường nội suy.
Độ phức tạp: Giảm còn $O(n \cdot bw)$.