竞赛讨论区 > 【每日一题】7月13日题目精讲—Kingdom
头像
是瑶瑶呀
编辑于 2020-07-13 12:00
+ 关注

【每日一题】7月13日题目精讲—Kingdom


活动时间:7月7日起至9月1日
活动内容:写满30篇每日一题的题解
活动奖励:即可额外获得牛客T恤一件
活动目的:滴滴滴~想充实的过完这个暑假嘛~快来写每日一题~每天都要进步喔~提升自己的同时还有超多福利喔~


每日一题交流群,群内定期有福利发放,群号:659028468

今日每日一题预告
【每日一题】7月13日题目预告
题号 NC19810
名称 kingdom
来源 牛客国庆集训派对Day6
戳我进入往期每日一题汇总贴~
往期每日一题二期题单

图片说明

如果你在题库做题时遇到了喜欢的题目,欢迎推荐给邓老师~ 点击查看详情

题解

我们先根据题意一步一步分析,由于只是给出树的节点个数,树可以由我们任意构造,我们假设n个节点取得答案最大的时候树长这样

图片说明
根节点root,连接着k个子树,k个子树大小分别为sum1,sum2.....sumk,有
(sum1+sum2+..+sumk+1)=n
我们令ans[n]为n个节点的树所得的最优解
root的“心腹”其实就是root的重儿子,我们root的重儿子是所在子树是X,重儿子中全部节点到root的费用,是不是就是ans[sumX],因为经过重儿子的边到父节点不会有任何影响。如果不是重儿子的所在子树Y(Y不等于X),这个子树的全部节点到root的贡献,是否都需要+1(题意转换,不理解的话仔细读题),因此这个子树的全部点到root的费用,就是ans[sumY]+sumY,sumY个节点,每个都经过边一次。因此,我们可以得出一个结论,
假设重儿子所在子树为X,有
ans[n]=(ans[sum1]+ans[sum2]+...+ans[sumk])+(n−sumX−1)
这里的减1是减去root这个根节点。
这里我们设一个二维数组,dp[i][j]表示 i个节点组成的森林(多个树),且节点最多的那个树节点数不超过j,注意!!!注意!!!是森林,森林,森林,重要的事情要说三遍!!!!可能不止一棵树,上图
图片说明
那么现在问题是如何维护ans[]和dp[][]这两个数组?
由上面那幅图我们可以清晰得出,只要枚举n个节点的重儿子所在子树的节点树sumX,
然后可以得到一个可能结果
dp[n−sumX−1][sumX]+n−sumX−1+ans[sumX]
因此,对于ans[n],只需要枚举sumX不断更新,取最大值,得出公式
ans[n]=dp[n−1−sumX][sumX]+n−1−sumX+ans[sumX],且1<=sumX<n
现在只剩下dp[][]数组了,我们来看,dp[i][j],节点总数为i,最大树节点数小于等于j的森林,有以下两种可能:
1.dp[i][j]=dp[i][j−1] ,小于等于j-1必定小于等于j,可以直接更新
2.dp[i][j]=dp[i−x][j]+ans[x] ,x<=j, 由一棵节点数为x的树和一个节点总数为i-x的森林,且这个森林的节点最多的那棵树不超过j 组成 节点总和为i,节点最多的树不超过j的森林
取上面两种情况的最小值即可,由于数据是8000,复杂度不能超过n^2,第一重for循环肯定是枚举节点总数i = 1~n,然后枚举sumX,求得ans[i],然后更新dp[][],由于dp和ans[x]这一变量有关,类似于完全背包,在枚举的时候会得到一个新的物品ans[i],枚举放入这个背包,背包容量是n,然后更新即可,完结,撒花★,°:.☆( ̄▽ ̄)/$:.°★ 。

感谢@fuzhiji同学提供的题解,奖励牛币100已发放~

活动奖励:

在牛客博客中写出题解,并回复地址
审核通过可获得(依据题目难度和题解的内容而定)

本道题目7月20日中午12:00之前写的题解有获得牛币资格~

.牛币兑换中心

牛客博客开通方式

  1. 如何开通牛客博客:https://www.nowcoder.com/discuss/202952
  2. 如何使用博客搬家功能:进入博客--->设置--->底部博客搬家
  3. 如果你对牛客博客有任何意见或建议:牛客博客意见反馈专贴

全部评论

(18) 回帖
加载中...
话题 回帖

本文相关内容

等你来战

查看全部

热门推荐