A6998 | $Game With Triangles: Season 2$

时间限制1s

内存限制128MB

通过 / 提交0/0

题目描述

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$。

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

输入 #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

C++ 编辑器

输入

输出