Bài 3. Bắn bi (OLP MT&TN lần 7)
Xem PDFSau khi hoàn thành kỳ thi kết thúc học phần đầy căng thẳng tại trường VH, nhóm bạn trẻ rủ nhau xả stress bằng việc chinh phục Zuma – tựa game bắn bi kinh điển.
Trong màn chơi hiện tại, trên màn hình xuất hiện một hàng gồm \(N\) viên bi nối tiếp nhau đang lăn tới lỗ hổng. Viên bi thứ \(i\) (tính từ trái sang phải) có màu sắc được quy ước bởi một số nguyên dương \(A_i\).
Quy luật của trò chơi như sau: Trong mỗi lượt thao tác, người chơi được phép ngắm bắn để chọn một đoạn các viên bi liên tiếp có cùng màu và làm cho chúng nổ tung. Ngay sau khi đoạn này biến mất, phần còn lại ở hai phía sẽ lập tức trượt lại gần nhau và nối liền thành một hàng mới.
Yêu cầu: Hãy tính toán số lượt bắn bi ít nhất để nhóm bạn có thể phá hủy toàn bộ \(N\) viên bi và vượt qua màn chơi một cách hoàn hảo.
Input
- Dòng đầu tiên chứa một số nguyên dương \(N\) (\(1 \le N \le 500\)) là số lượng viên bi ban đầu.
- Dòng thứ hai chứa \(N\) số nguyên dương \(A_1, A_2, \dots, A_N\) (\(1 \le A_i \le 100\)) là màu sắc của các viên bi từ trái sang phải.
Output
- In ra một số nguyên duy nhất là số lượt bắn ít nhất cần thực hiện để dọn sạch toàn bộ \(N\) viên bi.
Example
Test 1
Input
5
1 2 3 2 1Output
3Note
- Bước 1: Phá hủy viên bi màu 3 ở vị trí số 3. Dãy bi chập lại thành:
1 2 2 1. - Bước 2: Phá hủy đoạn 2 viên bi màu 2 ở giữa. Dãy bi chập lại thành:
1 1. - Bước 3: Phá hủy đoạn 2 viên bi màu 1 còn lại. Toàn bộ dãy bi bị tiêu diệt. (Tổng cộng 3 thao tác).
Test 2
Input
7
1 2 1 2 1 2 1Output
4Note
Một trong những cách tối ưu là phá hủy lần lượt 3 viên bi màu 2 (tốn 3 thao tác). Sau đó 4 viên bi màu 1 sẽ chập lại thành một đoạn liên tiếp 1 1 1 1. Cuối cùng chỉ cần 1 thao tác để phá hủy tất cả. (Tổng cộng 4 thao tác).
Scoring
- Subtask \(1\) (\(15\) điểm): \(N \le 10\).
- Subtask \(2\) (\(15\) điểm): \(N \le 20\).
- Subtask \(3\) (\(20\) điểm): \(N \le 50\).
- Subtask \(4\) (\(20\) điểm): \(A_i \le 2\) với mọi \(1 \le i \le N\).
- Subtask \(5\) (\(30\) điểm): Không có ràng buộc nào thêm.
Bình luận (2)