#232. 消木块

消木块

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

你们中的一些人可能玩过一个叫做消木块的游戏。

n\red {n}个木块排成一列,每个木块都有一个颜色。

例如下图中木块的颜色分别为:金,银,银,银,银,铜,铜,铜,金。

img

每次,你都可以点击一个木块,这样被点击的木块以及和它相邻并且同色的木块就会消除。

如果一次性消除了k\red {k}个木块,那么就会得到k×k\red {k\times k}分。

例如下图所示,点击银色木块,四个木块被消去,得到16\red {16}分。

img

给定你一个游戏初始状态,请你求出最高得分是多少。

输入格式

第一行包含整数t\red {t},表示共有t\red {t}组测试数据。

每组数据第一行包含整数n\red {n},表示共有n\red {n}个木块。

第二行包含n\red {n}个整数,表示n\red {n}个木块的颜色。

代表木块颜色的整数范围是1n\red {1\sim n}

输出格式

每组数据输出一个结果,每个结果占一行。

输出格式为Case x:y\red {“Case ~x: y”},其中x\red x为数据组别编号,从1\red {1}开始,y\red {y}为结果。

样例

输入样例

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

输出样例

Case 1: 29
Case 2: 1

提示

1n200\red {1≤n≤200}

DP测试

未参加
状态
已结束
规则
IOI
题目
7
开始于
2023-4-16 18:00
结束于
2023-4-18 5:00
持续时间
35 小时
主持人
参赛人数
12