[SDOI2017]苹果树 题解
时间:2022-03-12 20:43
首先,观察题意,可以发现在最长链下再接一个点,结果一定更优。
也就是说,可以免费选一条最长链,之后正常选。
我们枚举选的最长链,然后算出剩下部分的最优解。
有4部分:
1、链上每个点都选一个。
2、链上剩下的部分。
3、链的左面。
4、链的右面。
1可以直接计算。
那么,我们需要先进行树形背包,然后再通过某方式将其余3个合并。
我们知道,在此问题中,合并2个背包是\(O(k)\)的;
但3个及以上则是\(O(k^2)\)的,无法承受。
所以,我们只能在计算中就把其中两个合并,这样就只需合并2个了。
可以发现,3和4是正常的树形背包,而2是一个贪心的问题。
但是,我们没有时间给链上的点排序,再贪心选择。
所以,只能将2转为正常的树形背包问题。
可以这样想:选x则要选fx,选x的第二个则要选x的第一个。
那么,我们可以把大于1的拆点,拆成1和a-1。连上父子关系。
不难发现,这样我们就只需要3,4两个合并了。
先考虑如何进行树形背包:
树形背包有2种实现:dfs合并的和dfs序上dp的。
由于本题每个节点上有多个,所以之前的\(O(nk)\)的分析不适用,复杂度是\(O(nk^2)\),显然超时。
而且,复杂度的瓶颈合并背包至少是\(O(k^2)\)的,这个是max卷积,不能优化。
所以,这种方法不行。
但是,由于我们不需要知道每个节点的子节点的选择信息(如每个点选择了多少子树节点),
所以,可以考虑dfs序上dp的算法。
这个算法的状态数是\(O(nk)\)的,且相当于逐渐添加,没有合并背包。
添加的过程是一个多重背包,可以用单调队列优化。
坑
相关推荐
- Android系统编程入门系列之界面Activity交互响应
- 新型横向移动工具原理分析、代码分析、优缺点以及检测方案
- uni-app滚动视图容器(scroll-view)之监听上拉事件
- uniapp h5,app两端复制文本
- Android系统编程入门系列之界面Activity响应丝滑的传统动画
- 【Azure 应用服务】App Service 配置 Application Settings 访问Storage Account得到 could not be resolved: '*.file.core.windows.net'的报错。没有解析成对应中国区 Storage Account地址 *.file.core.chinacloudapi.cn
- 诺基亚短信生成!太好玩了
- iOS 跳转App Store进行评分
- 开发一个即时通讯App
- 关闭苹果IOS app自动更新
电脑软件
本类排行
- 1关闭苹果IOS app自动更新
- 2iOS 跳转App Store进行评分
- 3诺基亚短信生成!太好玩了
- 4Android系统编程入门系列之界面Activity响应丝滑的传统动画
- 5uniapp h5,app两端复制文本
- 6uni-app滚动视图容器(scroll-view)之监听上拉事件
- 7新型横向移动工具原理分析、代码分析、优缺点以及检测方案
- 8Android系统编程入门系列之界面Activity交互响应
- 9开发一个即时通讯App
- 10【Azure 应用服务】App Service 配置 Application Settings 访问Storage Account得到 could not be resolved: '*.file.core.windows.net'的报错。没有解析成对应中国区 Storage Account地址 *.file.core.chinacloudapi.cn