← 返回题目列表

Codeforces · 2074/G

G. 三角形游戏:第 2 季

中文机器翻译题面 查看原题
主唱迎接您进入生存游戏的最后一轮。

有一个正多边形,边长为 $$$n$$$ ($$$n \ge 3$$$)。顶点按顺时针顺序索引为 $$$1,2,\ldots,n$$$。在每个顶点$$$i$$$上,粉红色的士兵都写下了一个正整数$$$a_i$$$。有了这个正多边形,您将玩一个定义如下的游戏。

最初,您的分数为 $$$0$$$。然后,您可以多次执行以下操作来增加您的分数。

  • 选择 $$$3$$$ 不同的顶点 $$$i$$$、$$$j$$$、$$$k$$$ 尚未选择 之前,绘制由三个顶点组成的三角形。
    • 然后,您的分数增加 $$$a_i \cdot a_j \cdot a_k$$$。
    • 但是,你 无法执行此操作 如果该三角形与之前绘制的任何三角形共享正公共面积。
左侧是两次操作后的状态示例。右边的状态 是不可能的 因为两个三角形共享一个正公共面积。

您的目标是最大化分数。请找出您可以从该游戏中获得的最高分数。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。

每个测试用例的第一行包含一个整数 $$$n$$$ — 顶点数 ($$$3 \le n \le 400$$$)。

每个测试用例的第二行包含 $$$a_1,a_2,\ldots,a_n$$$ - 写在顶点上的整数 ($$$1 \le a_i \le 1000$$$)。

保证所有测试用例的$$$n^3$$$总和不超过$$$400^3$$$。

输出

对于每个测试用例,在单独的行中输出您可以获得的最高分数。

示例

输入
复制

6
3
1 2 3
4
2 1 3 4
6
2 1 2 1 1 1
6
1 2 1 3 1 5
9
9 9 8 2 4 4 3 5 3
9
9 9 3 2 4 4 8 5 3

输出
复制

6
24
5
30
732
696

注意

在第一个测试用例中,您只能绘制一个三角形。通过绘制三角形 $$$i=1$$$、$$$j=2$$$、$$$k=3$$$ 可以找到最高分 $$$6$$$。

在第二个测试用例中,您只能绘制一个三角形。通过绘制三角形 $$$i=1$$$、$$$j=3$$$、$$$k=4$$$ 可以找到最高分 $$$24$$$。

在第三个测试用例中,您可以绘制两个三角形。有一系列的两个操作导致得分$$$5$$$,这是最大值。

在第四个测试用例中,您可以绘制两个三角形。然而,绘制两个三角形会导致得分 $$$6+5=11$$$、$$$15+2=17$$$ 或 $$$10+3=13$$$。通过绘图找到最高分$$$30$$$ 只有一个 三角形,$$$i=2$$$、$$$j=4$$$、$$$k=6$$$。

在第五个测试用例中,您可以绘制三个三角形。最高分 $$$732$$$ 是通过如下绘制三个三角形得出的。