4279. [THUPC 2025 Final] 图，距离，最优化

【题目描述】

给定 $n$ 个非负整数 $x_1,x_2,\dots,x_n$。

对于任意 $n$ 个节点的无向连通图 $G$，将其节点由 $1$ 至 $n$ 标号，则其分数定义为 $$\text{score}(G) = \sum_{i=1}^n \sum_{j=i+1}^n \text{dist}_G(i, j)x_ix_j$$

其中 $\text{dist}_G(i,j)$ 表示图 $G$ 上 $i$ 到 $j$ 的最短路径长度。

你的任务是输出所有 $n$ 个节点的无向连通图中分数的最大值。

【输入格式】

本题有多组测试数据。输入的第一行一个整数 $t\ (1 \le t \le 300)$ 表示测试数据组数，接下来依次输入每组测试数据。

每组测试数据的的第一行一个整数 $n\ (1 \le n \le 300)$。

每组测试数据的第二行 $n$ 个整数 $x_1,x_2,\dots,x_n\ (0 \le x_i \le 2,000)$ 描述序列 $x$。

保证所有测试数据的 $n$ 的和不超过 $300$。

【输出格式】

对于每组测试数据输出一行一个整数，表示所有无向连通图中分数的最大值。

【输入样例】

3
2
1 2
4
1 0 1 1
7
1 2 3 4 5 6 7

【输出样例】

2
6
1044

【样例解释】

对于第一组测试数据，只有一种合法方案 $G = \{(1,2)\}$。

对于第二组测试数据，一个最优方案为 $G = \{(1,2),(2,3),(2,4)\}$。

【来源】

清华大学学生算法协会 GitLink 仓库