自动搬运

查看原文

来自洛谷，原作者为

	abruce I won't feel lonely, nor will I be sorrowful... not before everything is buried.

搬运于2025-08-24 22:33:34，当前版本为作者最后更新于2021-06-29 22:24:02，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

10pts

你爆搜出这棵树应该都可以过。

30pts

由 prufer 序列我们得知，对于一个度数的序列 $d$，如果 $\forall 1\le d_i<n,\sum d_i=2n-2$。那么就一定可以生成至少一棵树。
所以我们只需要构造出合法的 $d$ 序列，就可以求得最大值。
于是我们可以写出一个 $O(n^3)$ 的 dp：设 $f_{i,j}$ 为前 $i$ 个点放了 $j$ 的度数的最小代价。dp 转移方程：$f_{i,j}=\min\limits_{k=i-1}^{j-1}f_{i-1,k}+(j-k)^2v_i$。

50pts

对上面那个式子进行斜率优化。

100pts

$O(n^2)$ 状态数的 dp 很明显无法支持这个数据范围，我们考虑能否贪心。答案是可以的。
首先我们对于每个点先放一个度数，消除 $\forall 1\le d_i<n,\sum d_i=2n-2$ 的限制。然后把 $((d_i+1)^2-d_i^2)v_i$ 当成费用丢进堆里，一直选，每一次将选出来的 $d_i$ 加 $1$，更新贡献，选 $n-1$ 次就可以。
一个口胡的证明：如果当前你选了一个更劣的解，它解锁出来的一定也是更劣的解，所以不如就选当前最优解。
代码很好实现。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=3e5+5;
struct que {
	int w,v;
	que(int W,int V) {
		w=W,v=V;
	}
	friend bool operator<(que a,que b) {
		return (2*a.w+1)*a.v>(2*b.w+1)*b.v;//按照增加的费用排序
	}
};
int n,v[maxn];
ll ans;
priority_queue<que> q;
int main() {
	scanf("%d",&n);
	for(register int i=1; i<=n; i++)scanf("%d",&v[i]),ans+=v[i],q.push(que(1,v[i]));
	for(register int i=1; i<n-1; i++) {
		que u=q.top();
		q.pop();
		ans+=(2*u.w+1)*u.v;
		if(u.w<n-1)q.push(que(u.w+1,u.v));
	}
	printf("%lld",ans);
	return 0;
}