Hướng dẫn giải của Nhân viên cứu hộ (Platinum)

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: Nhân viên cứu hộ (Platinum)

Hướng tiếp cận

Bài toán yêu cầu sa thải đúng $K$ trong $N$ nhân viên sao cho tổng độ dài phần bao phủ của các đoạn còn lại là lớn nhất. Đây là bài toán quy hoạch động trên các đoạn thời gian.

Nhận xét quan trọng

Loại bỏ đoạn bị chứa: Nếu đoạn $[l_{i}, r_{i}]$ được chứa hoàn toàn trong đoạn $[l_{j}, r_{j}]$ (tức là $l_{j} \leq l_{i}$ và $r_{i} \leq r_{j}$ ), thì xóa $[l_{i}, r_{i}]$ không làm mất bao phủ nào. Gọi số đoạn bị chứa là free_removals. Ta dùng chúng ưu tiên để đạt K lần sa thải.
Sau khi lọc: Sắp xếp theo thời điểm bắt đầu và loại bỏ các đoạn bị chứa, tập còn lại $b$ có tính chất đơn điệu: cả điểm đầu lẫn điểm cuối đều tăng nghiêm ngặt.
Giảm bài toán: Sau khi dùng hết free_removals lần sa thải miễn phí, cần sa thải thêm need = K - free_removals đoạn từ tập $b$ .

Thuật toán

Quy hoạch động:

Định nghĩa $d p [i] [r]$ = bao phủ tối đa của $b [0 . . i]$ khi giữ $b [i]$ và sa thải đúng $r$ đoạn từ $b [0 . . i]$ .

Chuyển trạng thái: Với mỗi $j < i$ (đoạn liền trước được giữ):

Loại bỏ tất cả $b [j + 1 . . i - 1]$ (gồm $i - j - 1$ đoạn), nên $r = r_{j} + (i - j - 1)$ .
Đóng góp của b[i]:
- Nếu $b [j]$ và $b [i]$ rời nhau ( $r_{j} \leq l_{i}$ ): $contrib = r_{i} - l_{i}$
- Nếu chồng lấp: $contrib = r_{i} - r_{j}$ (vì $b$ đơn điệu, $r_{i} > r_{j}$ )
Ta chỉ cần xét $j \geq i - 1 - need$ (vì $i - j - 1 \leq need$ ).

Trường hợp cơ sở: $d p [i] [i] = r_{i} - l_{i}$ với $i \leq need$ (sa thải tất cả $b [0 . . i - 1]$ ).

Kết quả: ${max}_{i} d p [i] [need - (M - 1 - i)]$ , trong đó ta cũng sa thải $M - 1 - i$ đoạn $b [i + 1 . . M - 1]$ .

Độ phức tạp

Thời gian: O(NlogN+M·K2) với M≤N, K≤N.
- Trong thực tế, $K \leq 100$ trong các test của USACO, nên phần DP là $O (N \cdot K^{2})$ rất nhanh.
Bộ nhớ: $O (N \cdot K)$

Bình luận

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