Đổi màu


Submit solution

Points: 1
Time limit: 1.0s
Memory limit: 1G

Problem type

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

There are no comments at the moment.