3355. 开心消消乐

单点时限: 1.0 sec

内存限制: 256 MB

大家都玩过一种叫作开心消消乐的游戏。

规则很简单:刚开始有一列不同颜色的方块,每次可以消掉相邻的、颜色相同的若干个($k$ 个),并获得 $k^2$ 分。现在给出一个游戏的起始局面,问最多能获得多少分?

输入格式

第一行给出一个整数 $n$,表示起始的方块数。

第二行 $n$ 个整数 $a_1, a_2, \ldots, a_n$ $(1 \leq a_i \leq n)$,用空格隔开,依次表示这列方块的颜色。

数据规模约定:

  • 对于 $40\%$ 的数据,$1 \leq n \leq 10$。
  • 对于 $100\%$ 的数据,$1 \leq n \leq 100$。

输出格式

输出最多得分。

样例

Input
5
1 2 2 1 1
Output
13

提示

最佳方案是:

  • 先消掉中间的两个 2,获得 $4$ 分。
  • 在消掉连续的三个 1,获得 $9$ 分。

所以答案是 $4+9=13$ 分。

65 人解决,104 人已尝试。

87 份提交通过,共有 308 份提交。

4.4 EMB 奖励。

创建: 3 年前.

修改: 3 年前.

最后提交: 1 周,2 天前.

来源: 2017 直升研究生机试

题目标签