P4469.第1题-单元标注

1000ms

Difficulty: 7

所属公司 : 京东

算法与标签>动态规划

题目内容

某数据中心有一个包含N个连续存储单元的数组，初始时所有单元的标签均为“未标注”。数据管理员小明需要将这些单元标注为目标字列 $8$ ，其中 $B_i$ 表示第 $i$ 个单元的目标标签。

每次标注操作可以选择一个连续的区间 $[L,R]$ ，将该区间内所有单元的标签统一设为某个值 $x$ 。小明想知道要完成目标标注最少需要多少次操作?

第一行包含一个正整数 $N$ ，表示存储单元的数量

第二行包含 $N$ 个正整数，依次表示日标标签序列 $B$ ( $B_i$ 为第 $i$ 个单元的目标标签)。

$N≤400，1≤B_i≤N$

一行，一个正整数，表不最少需要的标注操作次数

输入

8
4 4 1 1 1 4 4 4

输出

说明

先将全范围标 4，再覆盖中间区域标为1，仅需两次操作

输入

预期输出（选填）