P1390. 方块游戏

问题描述

有些人可能玩过一个叫做“方块”的游戏。游戏中有一排方块，每个方块有一种颜色。例如：金、银、银、银、银、铜、铜、铜、金。

对应的图片如下图所示：

如果某些相邻的方块都是同一种颜色，并且其左边（如果存在）和右边（如果存在）的方块都是其他颜色，我们称其为一个“方块段”。总共有$4$个方块段。分别是：金色、银色、青铜色、金色。这些段中的方块数量分别是$$ 1、4、3、1$$ 个。

每次，你可以点击一个方块，然后包含该方块的整个段会消失。如果该段由 $k$ 个方块组成，你将获得 $k²$ 分。例如，如果你点击一个银色方块，银色段会消失，你会得到 $$4×4=16$$ 分。

现在看下面的图片：

第一个是最优解。

给定游戏的初始状态，找出可以获得的最高分数。

输入

第一行包含测试用例的数量$$ t（1 ≤ t ≤ 15）$$。每个测试用例包含两行。第一行包含一个整数 $$n（1 ≤ n ≤ 200）$$，表示方块的数量。第二行包含 $n$ 个整数，表示每个方块的颜色。整数范围是$1$ 到 $n$。

输出

对于每个测试用例，输出用例编号和可能的最高分数。

输入示例 1

2
9
1 2 2 2 2 3 3 3 1
1
1

输出示例 1

Case 1: 29
Case 2: 1

来源

Liu Rujia@POJ

如果需要进一步帮助，请告诉我！