A94859.Game With Triangles: Season 2

提高+/省选-

通过率：0%

时间限制：1.00s

内存限制：128MB

Frontman 欢迎你来到这场生存游戏的最终回合。给定一个具有 $n$ 条边的正则多边形（ $n \ge 3$ ），其顶点按顺时针顺序编号为 $1,2,\ldots,n$ 。每个顶点 $i$ 上被粉色士兵写有一个正整数 $a_i$ 。你需要基于这个正则多边形进行如下定义的游戏。

初始时你的得分为 $0$ 。你可以通过以下操作任意次来增加得分：

选择三个未被选择过的不同顶点 $i$ $i$ 、 $j$ $j$ 、 $k$ $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$ 。

对于每个测试用例，在单独一行中输出可获得的最大得分。

输入#1

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

输出#1

第一个测试用例中，只能绘制一个三角形。选择 $i=1$ 、 $j=2$ 、 $k=3$ 的三角形可得最大得分 $6$ 。

第二个测试用例中，只能绘制一个三角形。选择 $i=1$ 、 $j=3$ 、 $k=4$ 的三角形可得最大得分 $24$ 。

第三个测试用例中，可以绘制两个三角形。通过两次操作可得最大得分 $5$ 。

第四个测试用例中，可以绘制两个三角形。但绘制两次得分可能为 $6+5=11$ 、 $15+2=17$ 或 $10+3=13$ 。选择仅绘制 $i=2$ 、 $j=4$ 、 $k=6$ 的三角形可得最大得分 $30$ 。

第五个测试用例中，可以绘制三个三角形。通过以下方式绘制三个三角形可得最大得分 $732$ ：