【2018.10.1】【JSOI2016】最佳团体(bzoj4753)
2024-09-30 02:34:31
一看到“比值”最大(性价比最高)就知道跟分数规划有关系了。(这里讲过分数规划)
然后看到 要选一个候选人 必须选他的前置,画画图就知道是一棵树。
所以这道题是二分比值,每个点的权值就是战斗力-费用*比值,然后判断在树上能否得到权值和$\geq 0$的方案。
那怎么判断?
这篇的T1讲过,典型的树上背包,像那道T1一样在树上暴力转移即可。其实这题的父子依赖性质跟那道T1差不多,因为连通块就是一片父子的依赖关系(当然最上边的根节点的祖先是还没处理到的)。
那树上每个点都要遍历一下它的所有儿子,对于每个儿子还要枚举以这个儿子为根的子树中选出的点的数量。
二分的时间复杂度是$O(log(ans))$,转移的时间复杂度$O(n^2)$。总时间复杂度是$O(n^2*log(ans))$。
这里证明一下转移的时间复杂度:
直观上看是$i,j,k$三重循环。
但是每个儿子的$n^2$个dp值只会更新给它的父亲。
换句话说,有一重循环是枚举儿子,而这是一棵树,每个儿子(也就是每个点)只会被枚举一次。
所以枚举儿子的循环是常数复杂度。
树上背包的时间复杂度就是$O(n^2)$而不是$O(n^3)$。
update:这是另一个大佬写的T2(此题)题解。
最新文章
- 从PHP底层源码去深入理解数组,并用C模拟PHP关联数组(原创)
- [译]学习HTTP协议的请求行
- [Android] android .keystore文件转x509pem工具
- AngularJs ngReadonly、ngSelected、ngDisabled
- September 28th 2016 Week 40th Wednesday
- 设计模式--外观(Facade)模式
- Linux 汇编语言开发指南
- vm虚拟机Kali2.0实现与物理机之间的文件拖动共享
- antlr v4 使用指南连载2——准备环境
- Nodejs经验谈
- Coroutine的原理以及实现
- Python开发【第十一篇】:MySQL
- C语言实例:函数指针
- Python Microsoft Visual C++ 10.0 is required (Unable to find vcvarsall.bat)
- IDEA使用技巧:CamelCasePlugin插件
- Hadoop学习之路(三)Hadoop-2.7.5在CentOS-6.7上的编译
- SSM搭项目报错:HTTP Status 400 – Bad Request
- 压缩的问题-----WriteUp
- (转,记录用)jQuery页面加载初始化的3种方法
- 基于LumiSoft.Net.dll发、收、删邮件