Hướng dẫn giải của Giá sách (Khó)

Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.

Tác giả: huunguyen

Lời giải: Giá sách (Khó)

Hướng tiếp cận

DP tối ưu $O (N \log N)$ với kỹ thuật gộp khoảng và cây tìm kiếm nhị phân.

Nhận xét quan trọng

Cùng công thức DP như bài Silver: $d p [i] = {min}_{j} (d p [j] + max (h_{j + 1 . . i}))$ với ràng buộc tổng chiều rộng.
Khoảng gộp: Khi xử lý sách $i$ , các $j$ có $max (h_{j + 1 . . i}) < h_{i}$ sẽ được gộp chung vào một khoảng mới (max = $h_{i}$ ). Tổng số lần gộp trên toàn bộ quá trình là $O (N)$ .
DP đơn điệu: $d p [j]$ tăng theo $j$ , nên $d p_{m i n}$ của mỗi khoảng là $d p [j_{l e f t}]$ .
Dùng multiset để tra cứu $min (d p [j] + m a x_h)$ qua các khoảng còn hiệu lực trong cửa sổ chiều rộng.

Thuật toán

Duy trì stack khoảng (max_h giảm dần từ đáy lên đỉnh).
Khi thêm sách $i$ : gộp các khoảng có maxh ≤ hi vào khoảng mới.
Cửa sổ trượt: loại các $j$ không còn hợp lệ (tổng chiều rộng vượt $L$ ).
$d p [i] =$ phần tử nhỏ nhất trong multiset.

Độ phức tạp

Thời gian: $O (N \log N)$
Bộ nhớ: $O (N)$

Bình luận

Không có bình luận tại thời điểm này.