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

fish_love_cat · 2025-04-09 14:27:32 · 题解

首先答案与给出的节点顺序无关，考虑降序排序。

我们猜想 G 最优时一定是一棵树。

证明：

如果说 G 已经是一棵树了，再加一条边一定会多一条路径，那么最短路径一定不会变长，相反可能变的更加不优秀。

于是最优情况下 G 一定是树。

进一步猜想 G 最优时一定是一条链。

证明：

如果说 G 已经是一条链了，我们把其中一段截出来接在某个度已经为 2 的点上使其成为一个树，距离显然是会变小的，与其这样做令该点试图贪两头贡献，不如尽可能延长距离最大化答案。

于是最优情况下 G 一定是链。

现在可以直接当序列来做了。

于是想到把最大值放两头贪心构造序列，但是这连样例都过不了。

为了最大化距离，我们对于大的数字放在左右两头显然是比放中间优秀的。

发现只用分讨两种情况，所以我们大力 dp 即可。

注意极小值要足够小，不然会出现这种东西。

答案很大要开 long long。

多测清空。

做完了。

#include<bits/stdc++.h>
#define int long long
using namespace std;
int a[305],b[2][600005];
bool cmp(int x,int y){
    return x>y;
}
void solve(){
    int n;
    cin>>n;
    a[0]=0;//多测清空多测清空多测清空多测清空多测清空
    for(int i=1;i<=n;i++)
        cin>>a[i],a[0]+=a[i];
    sort(a+1,a+1+n,cmp);
    for(int i=0;i<=a[0];i++)
        b[0][i]=b[1][i]=-114514;
    b[0][0]=0;
    b[1][0]=0;
    int m=0;
    for(int i=1;i<=n;i++){
        m+=a[i];
        for(int j=0;j<=m;j++){
            int ret=m-j-a[i];
            ret=b[(i+1)&1][j]+ret*(a[0]-ret);
            if(j>=a[i])ret=max(ret,b[(i+1)&1][j-a[i]]+j*(a[0]-j));
            b[(i)&1][j]=ret;
        }
    }
    int ans=0;
    for(int i=0;i<=a[0];i++)
        ans=max(ans,b[n&1][i]);
    cout<<ans<<'\n';
}
signed main(){
    int t;
    cin>>t;
    while(t--)solve();
    return 0;
}