牛客练习赛89 D.牛牛种小树(dp)

牛牛种小树

https://ac.nowcoder.com/acm/contest/11179/D

Description

给出 个点,构造一个生成树,其中某个点如果度数为 会提供 的贡献,求所能构造的最大贡献。

Solution

生成树有 条边,每条边会提供两个度数,于是总的度数一定是 。此外每个点必须满足度数大于等于1,不妨先给每个点先分配度数 ,之后类似于背包做 ,容量为 ,求所能分配的最大值即可。

Code

https://ac.nowcoder.com/acm/contest/view-submission?submissionId=48828025

一些比赛的题解 文章被收录于专栏

一些比赛的题解

全部评论

相关推荐

评论
4
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务