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

· · 题解

好玩。

但是关于大数放两边的结论，怎么没有严谨证明啊，来补一个。

思路

我们不难发现，排成一条链一定是优秀的，因为这样任意两点之间的最短路才能尽可能大。

问题是怎么排呢？我们考虑重新写出该式子。设 y_i 为从左往右第 i 个点的权值。则：

\begin{aligned} \text{score}(G)&=\sum_{i=1}^n\sum_{j=i+1}^n(j-i)y_iy_j\\ &=\sum_{i=1}^n\sum_{j=i+1}^n\sum_{k=i}^{j-1}y_iy_j\\ &=\sum_{1\le i\le k<j\le n}y_iy_j\\ &=\sum_{k=1}^{n-1}\sum_{i=1}^k\sum_{j=k+1}^ny_iy_j\\ &=\sum_{k=1}^{n-1}(\sum_{i=1}^ky_i)\times (\sum_{j=k+1}^ny_j)\\ &=\sum_{k=1}^{n-1}s_k\times (s_n-s_k) \end{aligned}

其中 s_i=\displaystyle\sum_{j=1}^iy_i。也就是说，枚举每一个断点，并计算前后缀和之积再求和。

这毫无疑问是一个进步，但是我们仍然不知道怎么排列最好。

考虑到：如果交换 y_i,y_{i+1} 会使答案变大，那么这一定不是最优解，考虑记 a=s_{i-1},b=s_n-s_{i+1}，则交换前后：

\begin{aligned} &\text{score}(G')-\text{score}(G)\\ =&a(y_i+b)+(a+y_{i+1})b-a(y_{i+1}+b)-(a+y_i)b\\ =&a(y_i-y_{i+1})+(y_{i+1}-y_i)b\\ =&(a-b)(y_i-y_{i+1}) \end{aligned}

若 \text{score}(G')\le \text{score}(G)，则 a-b 与 y_i-y_{i+1} 同号。

注意到随着 i 增加，a 在增加，而 b 在减少，因此一开始 a-b<0，在中间转变为 a-b>0。因此得出结论：

最优的 \{y_i\} 没有局域极大值。

或者说，\{y_i\} 一定是先减后增。

这毫无疑问给了我们启发。不妨从大往小填数，那么一定是从两边往中间填，已经填入的部分是一个前缀和一个后缀。如下：

xxx...xx???...??xxx...xx

其中 x 是已填入的，? 是未填入的。

在填入下一个数时（用 ! 表示，假设它填在前缀，且是第 k 位）：

xxx...xx!??...??xxx...xx

我们可以直接计算贡献 s_k\times (s_n-s_k)——只要知道前缀所有数之和。

填在后面也是同样的。不多论述。注意只要填完前 n-1 大的数即可，这时贡献已经计算完了。

设 dp_{i,j} 表示已经填入前 i 大的数，且填在前缀的数之和为 j 时的最大分数。记 p_i 表示前 i 大的数之和。

设当前填入的数为 x，则：

于是得出转移式：

dp_{i,j}=\max(dp_{i-1,j-x}+j\times (s_n-j),dp_{i-1,j}+(p_i-j)\times (s_n-p_i+j))

只需 O(n^2\max{x_i}) 时间复杂度即可完成，使用滚动数组做到空间复杂度 O(n\max{x_i})。

如果只用一个滚动数组（类似于背包），请注意特判 x_i=0 的情况。

代码

#include <bits/stdc++.h>
#define ll long long

using namespace std;

const int maxn = 305, maxv = 2005;

int a[maxn];
ll dp[maxn * maxv];

int main(){
    int T;
    scanf("%d", &T);
    while(T --){
        int n;
        scanf("%d", &n);
        int sum = 0;
        for(int i = 1; i <= n; i ++) scanf("%d", &a[i]), sum += a[i];
        for(int i = 1; i <= sum; i ++) dp[i] = -1;
        sort(a + 1, a + n + 1);
        int pre = 0;
        for(int t = n; t >= 2; t --){
            pre += a[t];
            for(int i = pre; i >= 0; i --){
                if(a[t] > 0){
                    if(dp[i] >= 0) dp[i] += 1ll * (pre - i) * (sum - pre + i);
                    if(i >= a[t] && dp[i - a[t]] >= 0) dp[i] = max(dp[i], dp[i - a[t]] + 1ll * i * (sum - i));
                }else if(dp[i] >= 0) dp[i] += max(1ll * (pre - i) * (sum - pre + i), 1ll * i * (sum - i));
            }
        }
        ll ans = 0;
        for(int i = 0; i <= sum; i ++) ans = max(ans, dp[i]), dp[i] = 0;
        printf("%lld\n", ans);
    }
    return 0;
}