TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  问题讨论与解答  统计信息与排名
  • 首页
  • 题库
  • P3698
  • 题目
  • P3698方块消除
    限制 : 时间限制 : - MS   空间限制 : 65536 KB
    评测说明 : 时限1000ms
    问题描述

    有n个带颜色的方块排成一排,相同颜色的方块连成一段同色区域,如下图所示:


    游戏时,玩家可以任选一段同色区域,将其消去。设消去的这段包含x个相同颜色的方块,则此次消除操作的得分为x^2。然后右边的所有方块会往左边合拢。
    如下图所示:

    第一步将白色一段消除,得分16;
    第二步将褐色一段消除,得分9;
    第三步将橙色一段消除,得分4;
    总分29
    你的任务是对于给定的一排方块,计算消除它们能得到的最大得分。

    输入格式

    第一行,一个整数n
    第二行,描述初始状态的一排方块,由n个空格间隔的整数表示,每个整数表示一种颜色。整数的范围在[1,n]

    输出格式

    一行,一个整数,表示最大得分

    样例输入 1

    9
    1 2 2 2 2 3 3 3 1

    样例输出 1

    29

    样例输入 2

    8
    1 2 2 3 1 3 2 1

    样例输出 2

    18

    提示

    1<=n<=200


    来源  改编自uva10559