Đổi màu
Cho $N$ khối ô vuông được đặt liên tiếp trên một dãy hàng ngang. Mỗi ô vuông sẽ được tô lên với màu $c_i$. Một tập hợp gồm các ô liên tiếp được gọi là một vùng nếu tất cả các ô đó có cùng màu.
Bạn được phép xuất phát từ bất kì ô vuông nào trên dãy, sau đó mỗi thao tác là biến đổi tất cả các ô chung vùng với nó sang một màu khác bất kì (vùng biển đổi màu phải chứa ô xuất phát).
Tìm cách đưa tất cả các khối về cùng màu với ít thao tác nhất.
Dữ liệu
- Dòng đầu tiên chứa số nguyên $N \ (0< N \le 5000)$;
- Dòng tiếp theo chứa $N$ số nguyên $c_i \ (0<c_i \le 10^5)$.
Kết quả
- Số thao tác nhỏ nhất.
Chấm điểm
10;Màu của các vùng là phân biệt. 20;$N\le18$. 30;Có tối đa 2 màu. 40;Không có giới hạn gì thêm.
Ví dụ
Ví dụ 1
input
4
5 2 2 1
output
2
Ví dụ 2
input
8
4 5 2 2 1 3 5 5
output
4
Comments