Dọn Kho
Xem PDFĐề bài
Một kho hàng có \(n\) kiện xếp thành một hàng, đánh số từ \(1\) đến \(n\) từ trái sang phải. Kiện thứ \(i\) thuộc loại \(c_i\).
Mỗi lượt dọn kho, nhân viên chọn một đoạn liên tiếp gồm các kiện cùng loại trong hàng hiện tại rồi chuyển toàn bộ đoạn đó ra ngoài. Sau khi chuyển đi, các kiện còn lại giữ nguyên thứ tự cũ và dồn sát lại với nhau, nên hai kiện vốn không kề nhau có thể trở thành kề nhau.
Chuyển đi một đoạn gồm đúng \(t\) kiện tốn chi phí \(p_t\).
Hãy tìm tổng chi phí nhỏ nhất để chuyển hết toàn bộ \(n\) kiện ra ngoài.
| 1 | 2 | 2 | 1 | 1 |
|---|---|---|---|---|
| 1 | 2 | 3 | 4 | 5 |
Ví dụ 1, đáp số 7.
Example
Test 1
Input
5
1 2 2 1 1
10 3 4 5 6
Output
7Note
hàng ban đầu là 1 2 2 1 1. Trước hết chuyển đi đoạn gồm hai kiện loại 2 với chi phí \(p_2\) = 3. Hàng còn lại là 1 1 1, chuyển đi cả ba kiện cùng lúc với chi phí \(p_3\) = 4.
Tổng chi phí là 7.
Nếu chuyển từng kiện một thì tốn 5 · \(p_1\)=50, kém hơn hẳn
Test 2
Input
1
1
5
Output
5Note
chỉ có một kiện nên chi phí bằng \(p_1\) = 5.
Scoring
- Subtask 1 (25 points): \(n \le 100\)
- Subtask 2 (25 points): Mỗi màu xuất hiện nhiều nhất 2 lần trong dãy
- Subtask 3 (20 points): \(p_t\) = 1 với mọi t
- Subtask 4 (40 points): Không có ràng buộc bổ sung
Bình luận