2120: 消消乐

题目描述


yzj最近迷上了一款名为《消消乐》的游戏,游戏规则如下: 有一段长度为n的小球串,每个小球都有一种颜色,每次你可以选择一段连续的且颜色都相同的小球消掉,消掉后你会得到值为长度的立方的积分,并且这段消除后左边的小球(如果存在的话)和右边的小球(如果存在的话)会自动拼接起来。现在你需要解决这样一个问题:告诉你每个小球的颜色,按照以上规则你能获得的最大积分是多少?

输入


第一行一个整数n,表示小球串的长度。 第二行n个整数表示,第i个整数a[i]表示第i个小球的颜色。 1 <= n <= 200, 1 <= a[i] <= n.

输出


输出一个整数表示你能获得的最大积分。

样例输入


3
2 2 2

样例输出


27

提示


浙江理工大学月赛2019年5月

来源/分类


浙江理工大学月赛

请先 登录 后评论
  • 0 关注
  • 0 收藏,557 浏览
  • 轩爸 提出于 2019-08-02 22:38

相似问题