祖玛 - 代码源竞赛平台

题目描述

蜗蜗面前有一排 $n$ 颗宝石，第 $i$ 颗宝石的颜色为 $c_i$。

每次操作，蜗蜗可以选择当前序列中的一段非空连续宝石。如果这一段的颜色序列正着读和反着读完全相同，就可以将这一段宝石全部删除。删除之后，两侧剩余的宝石会拼接在一起，形成新的序列。只含一颗宝石的段也可以删除。

请你求出删除所有宝石所需的最少操作次数。

输入格式

第一行包含一个整数 $n$，表示宝石的数量。

第二行包含 $n$ 个整数 $c_1,c_2,\ldots,c_n$，表示每颗宝石的颜色。

输出格式

输出一行一个整数，表示删除所有宝石所需的最少操作次数。

样例

6
1 2 3 2 1 4

2

样例解释

第一次删除前五颗宝石，它们的颜色序列为 $1,2,3,2,1$，正着读和反着读相同。

第二次删除剩下的最后一颗宝石，共需要 $2$ 次操作。原序列不能一次全部删除。

数据范围

对于 100% 的数据，保证 $1\le n\le 500$，$1\le c_i\le n$。