首页 > 牛牛种小树
开通博客写题解
头像 Kur1su
发表于 2021-09-26 14:23:05
Description 给出 个点，构造一个生成树，其中某个点如果度数为 会提供 的贡献，求所能构造的最大贡献。 Solution 生成树有 条边，每条边会提供两个度数，于是总的度数一定是 。此外每个点必须满足度数大于等于1，不妨先给每个点先分配度数 ，之后类似于背包做 ，容量为 ，求所能分 展开全文
去ta的博客 赞 (4) 回复(0) 收起
头像 RunningBeef
发表于 2021-09-26 15:39:54
题意 ①题意中的度指的是对于数中每个结点的边数和，实际上就是图中无向图结点的度②根据树的特点，每个结点度至少为1，且n个结点的有n-1条边，每条边连接两个点，对这两个点都有一个度的贡献，所以树的度的和为 2*(n-1)③问题转化为 对 n 个结点选择 1 ~ (n - 1) 的度数，在度数和为 2 展开全文
去ta的博客 赞 (3) 回复(2) 收起
头像 あおいSakura
发表于 2021-09-27 21:41:50
牛牛种小树 题目链接：nowcoder 225544 到主站看：https://blog.csdn.net/weixin_43346722/article/details/120517394 题目大意 要你构造一个 n 个节点的数，然后给出你 f(i)，要你最大化 ∑i=1~n f(d[i])。其中 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 我头发呢_
发表于 2021-10-07 19:58:22
一共有n个点，因此度数和为2*(n-1)，首先给每个点分一个度，保证最后形成的是一棵树。 分配n个度后还剩下m=2*(n-1)-n=n-1个度，剩下的这些度的最优分配方案用完全背包的方法dp求得。 背包的体积为m，每个物品的体积和价值分别为i-1（i个度有一个度在之前已经算过了）和w[i] 普通的完 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 ssllyf
发表于 2021-09-28 07:21:44
题目大意 给你n个点，f函数的值，现在你要构造一棵树，一个度数为k的点有f(k)点贡献，问你最大贡献 解题思路 对于一棵树，除了根节点每个点都有一个父亲节点，而一个点的度数就是父亲节点数量+子节点数量 那么可以先构造一颗所有点都连向1的数（1为根节点），且先不计算根节点的贡献，那么贡献就是(n-1 展开全文
去ta的博客 赞 (0) 回复(0) 收起
查看本题
查看本题讨论

相关比赛

等你来战

查看全部
牛客竞赛，专业的竞技算法训练平台

扫描二维码，进入QQ群

扫码关注“比赛自动姬”