题意简述

给定 $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$ 个节点的无向连通图中分数的最大值。

$1 \le n \le 300$，$0 \le x_i \le 2000$

解法

我们首先假设至少有两个 $x_i$ 不为 $0$，否则答案一定是 $0$。

定理 1：一定存在一棵树取到最大分数。

不是一棵树的 $G$ 删掉一条不改变连通性的边肯定会让 $\text{dist}_G(i,j)$ 变大，所以这个定理是显然的。不过只知道 $G$ 是一棵树还不足以解决本问题。

定理 2：一定存在一条链取到最大分数。

假设分数最大的 $G$ 是一棵树但不是一条链。以任一度数大于等于 $3$ 的点 $r$ 为根。不妨假设其度数为 $3$，三个子树为 $A,B,C$，子树根分别 $a,b,c$，子树的 $x$ 的和分别为 $x_A,x_B,x_C$。假设 $x_A \le x_B \le x_C$。

考察如下调整：删去 $(r,b)$ 加上 $(a,b)$。此时从 $C$ 和 $r$ 到达 $B$ 的距离增加 $1$（多经过 $a$），从 $A$ 到达 $B$ 的距离减少 $1$（少经过 $r$），其他距离均不变。

因此图的分数变化为 $(x_r+x_C-x_A)x_B$。当这个值大于 $0$ 的时候，我们就可以得到一个分数更大的方案，矛盾。

若 $(x_r+x_C-x_A)x_B = 0$，有两种情况：

• $x_B = 0$，此时子树 $B$ 里的所有点 $p$ 都有 $x_p = 0$。将这些点插入到任意两个 $x$ 不为 $0$ 的点 $a, b$ 的路径中（注意我们假设了至少有两个 $x$ 不为 0），这样一定会让分数变大。
• $x_A=x_B=x_C$ 且 $x_r=0$。此时我们尝试进行调整以最大化第二个目标 $\text{score}^\star(G) = \sum_i \sum_{j > i} \text{dist}_G(i,j)$。注意到这个就是所有 $x$ 都是 $1$ 的版本所以一定可以进行调整，而这样调整一定不改变 $\text{score}(G)$。

因此每次调整要么会提升 $\text{score}(G)$，要么 $\text{score}(G)$ 不变的同时 $\text{score}^\star(G)$ 增加，而两者均为正整数且有上界。故不断进行调整后必然到达一个 $(\text{score}(G), \text{score}^\star(G))$ 的局部最大值，此时无法进行以上调整，也就是不存在度数大于等于 $3$ 的点。证毕。

运用以上定理，我们此时的任务是把 $x$ 重排为 $x'$，最大化 $\sum_i \sum_{j>i} (j-i)x_ix_j$。

我们还需要以下有关这个问题的解的性质。

定理 3：一定存在一个单谷的重排 $x^\star$ 达到最大分数。

不妨假设 $x$ 两两不同且大于 $0$，这可以通过给每个数加上一些微小扰动完成。

若最优的重排 $x^\star$ 不是单谷的，则存在 $p$ 满足 $x^\star_{p-1} < x^\star_p>x^\star_{p+1}$。考虑两种调整：

• $\text{swap}(x^\star_{p-1},x^\star_p)$，分数增加 $(x^\star_p - x^\star_{p-1})(x_{p+1 \sim n} - x_{1 \sim p-2})$；
• $\text{swap}(x^\star_{p+1},x^\star_p)$，分数增加 $(x^\star_p - x^\star_{p+1})(x_{1 \sim p-1} - x_{p+2 \sim n})$

注意到两个增量的第一项都是正的，而两个第二项的和为 $x_{p-1}+x_{p+1}$ 也是正的，因此必然存在一个调整增大分数。证毕。

最后我们把分数式子稍微变换一下。

$$\begin{align*} \sum_i \sum_{j>i} (j-i)x_ix_j & = \sum_i \sum_{j>i} \sum_{k=i}^{j-1} x_ix_j \\ = & \sum_k \sum_{i \le k} \sum_{j > k} x_ix_j \\ = & \sum_k x_{1 \sim k} \times x_{k+1\sim n}, \end{align*}$$

也就是说分数等于每个位置的前缀和和后缀和的乘积的和。

由于最优解是单谷的，考虑从大到小依次加入每个 $x_i$，此时每个 $x_i$ 一定加在未加入的部分的第一个或最后一个。加入进去之后，可以确定一个前缀和（加在后面是确定后缀和，其实也就是确定了剩余位置的前缀和），也就确定了分数中一项的贡献。

因为分数只关心每个位置的前缀和是多少，依此设计 DP：设 $f_{i,j}$ 表示加入了前 $i$ 大数，加在前面的所有数的和为 $j$ 时分数的最大值。加在后面的数的和可以直接通过 $i$ 和 $j$ 推导出来。转移枚举第 $i+1$ 大数放在前面还是后面，加上对应项的贡献即可。

复杂度 $O(n^2 \max x_i)$。