Che Ô

Lời giải: Che Ô

Hướng tiếp cận

Quy hoạch động trên các vị trí đã sắp xếp, kết hợp tiền xử lý chi phí ô.

Nhận xét quan trọng

1. Vì ô được phép chồng lấp, ta có thể tiền xử lý: $C_w^{\prime }=min(C_w,C_{w+1},\dots ,C_M)$ (mua ô rộng hơn nếu rẻ hơn).
2. Sắp xếp các vị trí, bài toán trở thành chia thành các nhóm liên tiếp.

Thuật toán

1. Sắp xếp $N$ vị trí.
2. Tiền xử lý: $C_w^{\prime }={min}_{k\ge w}{C}_k$.
3. DP: $dp[i]$ = chi phí tối thiểu che $i$ vị trí đầu. $$dp[i]={min}_{0\le j<i}(dp[j]+C_{po{s}_{i-1}-po{s}_j+1}^{\prime })$$

Độ phức tạp

• Thời gian: $O(N^2+M)$
• Bộ nhớ: $O(N+M)$