3572. [USACO21Feb Gold]Modern Art 3

【题目描述】

厌倦了常规的二维画作（同时也由于作品被他人抄袭而感到失落），伟大的奶牛艺术家牛加索决定转变为更为极简主义的一维风格。她的最新画作可以用一个长为 $N$（$1 \leq N \leq 300$）的一维数组来描述，其中每种颜色用 $1\ldots N$ 中的一个整数表示。

令牛加索感到沮丧的是，尽管这样，她的竞争对手哞奈似乎已经发现了如何抄袭她的这些一维画作！哞奈会用一种颜色涂在一个区间上，等待颜料干了再涂另一个区间，以此类推。哞奈可以使用 $N$ 中颜色中的每一种任意多次（也可以不用）。

请计算哞奈抄袭牛加索的最新一维画作所需要的涂色的次数。

【输入格式】

输入的第一行包含 $N$。

下一行包含 $N$ 个范围在 $1 \ldots N$ 之内的整数，表示牛加索的最新一维画作每个方格上的颜色。

【输出格式】

输出抄袭这一画作所需要的最小涂色次数。

【样例输入】

10
1 2 3 4 1 4 3 2 1 6

【样例输出】

6

【样例说明】

在这个样例中，哞奈可以按下列方式进行涂色。我们用 $0$ 表示一个未涂色的方格。

• 初始时，整个数组均未被涂色：

  
  

  0 0 0 0 0 0 0 0 0 0
  

  
  

• 哞奈将前九个方格涂上颜色 $1$：

  
  

  1 1 1 1 1 1 1 1 1 0
  

  
  

• 哞奈在一个区间上涂上颜色 $2$：

  
  

  1 2 2 2 2 2 2 2 1 0
  

  
  

• 哞奈在一个区间上涂上颜色 $3$：

  
  

  1 2 3 3 3 3 3 2 1 0
  

  
  

• 哞奈在一个区间上涂上颜色 $4$：

  
  

  1 2 3 4 4 4 3 2 1 0
  

  
  

• 哞奈在一个方格上涂上颜色 $1$：

  
  

  1 2 3 4 1 4 3 2 1 0
  

  
  

• 哞奈在最后一个方格上涂上颜色 $6$：

  
  

  1 2 3 4 1 4 3 2 1 6
  

注意在第一次涂色时，哞奈可以同时在前九个方格之外将第十个方格也同时涂上颜色 $1$，这并不会影响最后的结果。

【数据规模与约定】

测试点 2-4 中，画作中仅出现颜色 $1$ and $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 没有额外限制。

【来源】

USACO 二月公开赛 Gold 组