CF2074G.Game With Triangles: Season 2

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

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

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

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

第一个测试用例中，只能绘制一个三角形。选择 $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$：

翻译由 DeepSeek R1 完成