Problem
Chloe gần đây đã cài đặt Zuma trên điện thoại của cô ấy. Người chơi được đưa cho một hàng n viên ngọc, viên thứ i có màu c
i. Mục đích của trò chơi — phá hủy tất cả các viên đá trong ít giây nhất có thể.
Trong một giây, Chloe có thể chọn bất kỳ chuỗi con nào (một chuỗi các viên đá liền kề) là một bảng màu và xóa nó. Sau khi loại bỏ chuỗi con này, các viên đá còn lại lại được dịch chuyển để tạo thành một hàng liên tục. Số giây tối thiểu cần thiết để phá hủy toàn bộ dòng là bao nhiêu?
Nhớ lại rằng một chuỗi (hoặc chuỗi con) là một đối xứng nếu nó đọc từ trái sang phải giống như từ phải sang trái. Trong trường hợp này, điều này có nghĩa là màu của viên đá đầu tiên bằng màu của viên đá cuối cùng, màu của viên thứ hai bằng màu của viên đá áp chót, v.v.
Đầu vào:
Dòng đầu tiên chứa một số nguyên n (1 ≤ n ≤ 500) — số viên đá ở hàng ban đầu.
Dòng thứ hai chứa n số nguyên, số thứ i bằng c
i (1 ≤ c
i ≤ n) &mdash ; màu của viên đá thứ i ở hàng ban đầu.
Đầu ra:
In một số nguyên duy nhất — số giây tối thiểu cần thiết để loại bỏ tất cả đá quý.
Ví dụ:
| Đầu vào |
Đầu ra |
3
1 2 1
| 1 |
3
1 2 3
| 3 |
7
1 4 4 2 3 2 1
| 2 |
Giải thích:
Trình tự trong ví dụ thứ ba là [1, 4, 4, 2, 3, 2, 1] -> [1, 4, 4, 1] -> []