Nhân viên cứu hộ (Platinum)

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

1. 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\le l_i$ và $r_i\le 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.

2. 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.

3. 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 $dp[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\le l_i$): $\text{contrib}=r_i-l_i$
  • Nếu chồng lấp: $\text{contrib}=r_i-r_j$ (vì $b$ đơn điệu, $r_i>r_j$)
• Ta chỉ cần xét $j\ge i-1-\text{need}$ (vì $i-j-1\le \text{need}$).

Trường hợp cơ sở: $dp[i][i]=r_i-l_i$ với $i\le \text{need}$ (sa thải tất cả $b[0..i-1]$).

Kết quả: ${max}_{i}dp[i][\text{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(N\log N+M·K^2)$ với $M\le N$, $K\le N$.
  • Trong thực tế, $K\le 100$ trong các test của USACO, nên phần DP là $O(N·K^2)$ rất nhanh.
• Bộ nhớ: $O(N·K)$