Modern Art 3

题目描述

Picowso 这位伟大的奶牛艺术家已经厌倦了标准的二维艺术作品（也对别人抄袭她的作品感到沮丧），于是决定转向更极简的一维风格。她最新的画作可以用一个长度为 $N$（$1 \leq N \leq 300$）的一维颜色数组来描述，其中每种颜色由范围 $1\ldots N$ 内的一个整数表示。 Picowso 十分沮丧地发现，她的竞争对手 Moonet 似乎连这些一维画作也能复制！Moonet 会用一种颜色涂刷一个连续区间，等待其干燥后，再涂刷另一个区间，如此反复。Moonet 可以任意次数使用这 $N$ 种颜色（也可能某些颜色一次也不用）。 请计算 Moonet 复制 Picowso 最新的一维画作所需的刷涂次数。

输入格式

第一行输入 $N$。 第二行包含 $N$ 个整数，范围在 $1 \ldots N$，表示 Picowso 最新一维画作中每个格子的颜色。

输出格式

输出复制该画作所需的最少刷涂次数。

10
1 2 3 4 1 4 3 2 1 6

6

提示

在这个例子中，Moonet 可以按如下方式涂刷数组。我们用 $0$ 表示未涂刷的格子。 最初，整个数组都未涂刷： 0 0 0 0 0 0 0 0 0 0 Moonet 用颜色 $1$ 涂刷前九个格子： 1 1 1 1 1 1 1 1 1 0 Moonet 用颜色 $2$ 涂刷一个区间： 1 2 2 2 2 2 2 2 1 0 Moonet 用颜色 $3$ 涂刷一个区间： 1 2 3 3 3 3 3 2 1 0 Moonet 用颜色 $4$ 涂刷一个区间： 1 2 3 4 4 4 3 2 1 0 Moonet 用颜色 $1$ 涂刷一个单独格子： 1 2 3 4 1 4 3 2 1 0 Moonet 用颜色 $6$ 涂刷最后一个格子： 1 2 3 4 1 4 3 2 1 6 注意，在第一次刷涂时，Moonet 也可以在涂刷前九个格子的同时把第十个格子涂成颜色 $1$，而不会影响数组的最终状态。 SCORING: 在测试点 2-4 中，画作中只会出现颜色 $1$ 和 $2$。 在测试点 5-10 中，对于每个 $1\le i\le N$，第 $i$ 个格子的颜色在范围 $\left[12\left\lfloor\frac{i-1}{12}\right\rfloor+1,12\left\lfloor\frac{i-1}{12}\right\rfloor+12\right]$ 之内。 测试点 11-20 没有额外限制。 题目来源：Brian Dean 和 Benjamin Qi

标签: USACO|2021|Gold

来源

USACO|2021|Gold