1114D. D. Flood Fill

\r\n

CF1114D. Flood Fill

\n

时限: 2 秒 | 内存: 256 MB | 输入: 标准输入 | 输出: 标准输出

\r\n

给定一排 $n$ 个彩色方格，从左到右编号为 $1$ 到 $n$。第 $i$ 个方格初始颜色为 $c_i$。

\r\n

我们称，如果 $c_i = c_j$，且对于所有满足 $i < k < j$ 的 $k$，都有 $c_i = c_k$，那么第 $i$ 个方格和第 $j$ 个方格属于同一个连通块。换句话说，从 $i$ 到 $j$ 的所有方格颜色都相同。

\r\n

例如，序列 $[3, 3, 3]$ 只有 $1$ 个连通块，而序列 $[5, 2, 4, 4]$ 有 $3$ 个连通块。

\r\n

现在在这排方格上玩“洪水填充”游戏，规则如下：

\r\n

游戏开始时，你可以任选一个起始方格（这一步不计入回合数）。
每一回合，你可以将包含起始方格的连通块的颜色更改为任意其他颜色。

\r\n

请你求出，最少需要多少回合，才能将整排方格变成同一种颜色。

\r\n

输入格式

\r\n

第一行包含一个整数 $n$（$1 \\le n \\le 5000$），表示方格的数量。

\r\n

第二行包含 $n$ 个整数 $c_1, c_2, \\ldots, c_n$（$1 \\le c_i \\le 5000$），表示每个方格的初始颜色。

\r\n

输出格式

\r\n

输出一个整数，表示最少需要的回合数。

\r\n

样例输入 1

\n

4\n5 2 2 1

\n

样例输出 1

\n

\n

样例输入 2

\n

8\n4 5 2 2 1 3 5 5

\n

样例输出 2

\n

\n

样例输入 3

\n

1\n4

\n

样例输出 3

\n

\n

提示

\r\n

在第一个样例中，一种达到最优的方法是选择第 $2$ 个方格作为起始方格，然后按如下方式操作：

\r\n

$[5, 2, 2, 1]$
$[5, 5, 5, 1]$
$[1, 1, 1, 1]$

\r\n

在第二个样例中，一种达到最优的方法是选择第 $5$ 个方格作为起始方格，然后依次将颜色变为 $2, 3, 5, 4$。

\r\n

在第三个样例中，序列已经全部为同一种颜色。

统计

递交统计

1114D. D. Flood Fill

信息

还没有账户？

登录