自动搬运

查看原文

来自洛谷，原作者为

	王奕清 没有我，你的生活会怎样？

搬运于2025-08-24 21:35:24，当前版本为作者最后更新于2020-10-15 21:51:27，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

这是一道很水的黑题。

但是，本题的题意十分难懂。注意：样例输入是错的，最后一个4是多出来的。

整个题目的意思大概是：

一个节点最多可以有 $k$ 条边连向儿子，每条边有一个权值 $a_i$ ，一条边 $(u,v)$ （ $u$ 是父亲， $v$ 是儿子）对答案的贡献是 $v$ 子树内叶子节点的 个数² $* a_i$

其中，每个节点可以连出的边的权值是固定的，也就是说，每一个节点，它向儿子连边时，可以选择的边都是一样的。现在告诉你有 $n$ 个叶子结点，问你最小的答案。$(n<=1000,k<=1000)$

思路很简单，就是一个记忆化搜索，$f[x][y]$ 表示现在有 $x$ 个叶子节点待填，已经连了 $y-1$ 条边出去，当然对边权排序是必要的，因为显然，我们要保证最小的边下面跟的叶子节点最多。

然后转移也十分容易，对每条边，只有两种选择：

1.连叶子，直接加上 $a_i$

2.连非叶子节点，先加上这条边的贡献，然后在继续递归就可以了。

所以，我们只需要枚举第二种情况时，该节点下面放几个叶子节点就ok了

时间复杂度：$O(nk)$

代码：

#include<bits/stdc++.h>
using namespace std;
int n,k,f[1005][1005],a[1005];
int dfs(int x,int y)
{
	if(x==1)
	{
		f[x][y]=a[y];
		return f[x][y];
	}//只剩一个节点
	if(y==k)return f[x][y]=dfs(x,1)+a[y]*x*x;
    //只剩一条边，必须是连非叶子节点
	if(f[x][y])return f[x][y];
	f[x][y]=dfs(x-1,y+1)+a[y];//直接连叶子
	for(int i=2;i<x;i++)//枚举
	f[x][y]=min(f[x][y],dfs(x-i,y+1)+a[y]*i*i+dfs(i,1));
	return f[x][y];
}
signed main()
{
	cin>>n>>k;
	for(int i=1;i<=k;i++)cin>>a[i];
	sort(a+1,a+k+1);
	printf("%d",dfs(n,1));
}