3355. 开心消消乐

单点时限: 1.0 sec

内存限制: 256 MB

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

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

输入格式

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

第二行 个整数 ,用空格隔开,依次表示这列方块的颜色。

数据规模约定:

  • 对于 的数据,
  • 对于 的数据,

输出格式

输出最多得分。

样例

Input
5
1 2 2 1 1
Output
13

提示

最佳方案是:

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

所以答案是 分。

27 人解决,55 人已尝试。

38 份提交通过,共有 184 份提交。

8.1 EMB 奖励。

创建: 2 年,1 月前.

修改: 2 年,1 月前.

最后提交: 4 月,1 周前.

来源: 2017 直升研究生机试

题目标签