首页 > 试题广场 >

消消乐

[编程题]消消乐

热度指数：1659 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

小v在vivo手机的应用商店中下载了一款名为“一维消消乐”的游戏，介绍如下：

1、给出一些不同颜色的豆子，豆子的颜色用数字（0-9）表示，即不同的数字表示不同的颜色；

2、通过不断地按行消除相同颜色且连续的豆子来积分，直到所有的豆子都消掉为止；

3、假如每一轮可以消除相同颜色的连续 k 个豆子（k >= 1），这样一轮之后小v将得到 k*k 个积分；

4、由于仅可按行消除，不可跨行或按列消除，因此谓之“一维消消乐”。

请你帮助小v计算出最终能获得的最大积分。

输入描述:

输入一行n个正整数，代表这一行中豆子的颜色及排列。

示例：

输入：1 4 2 2 3 3 2 4 1
输出：21

示例说明：
第一轮消除3，获得4分，序列变成1 4 2 2 2 4 1
第二轮消除2，获得9分，序列变成1 4 4 1
第三轮消除4，获得4分，序列变成1 1
第四轮消除1，获得4分，序列为空
总共得分21分