一道好题

P12052 [THUPC 2025 决赛] 图，距离，最优化 题解

本题解大部分搬运官方题解。
题目大意

给定 \(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\) 大数放在前面还是后面，加上对应项的贡献即可。
这里详细说一下这个 DP：

• 状态表示：\(dp[j]\) 表示加入了前 \(i\) 大数，加在前面的所有数的和为 \(j\) 时分数的最大值。
  
• 初始化：\(dp[0][0] = 0\)，\(dp[j] = -INF\)。
  
• 状态转移：将放前面和放后面取最大即可
  \[dp[j]=\max(dp[i - 1][j] + (pre - j - x_i)(sum - (pre - j - x_i), dp[i - 1][j - x_i] + j(sum - j))\]
  
• 答案：\(\max(dp[n][j])\)。
  

值得注意的是，在代码上，本题需要滚动数组。
复杂度 \(O(n^2 \max x_i)\)。
代码

[code]#include#define endl "\n"#define ll long longusing namespace std;const ll N = 310, M = 6e5 + 10, inf = 1e18;ll t, n, sum;ll ans, a[N], dp[2][M];bool cmp(ll x, ll y){        return x > y;}void solve(){        cin >> n;        sum = 0;        for (int i = 1; i > a;                sum += a;        }        sort(a + 1, a + n + 1, cmp);        for (int i = 0; i