LOJ2482 CEOI2017 Mousetrap 二分答案、树形DP
2024-10-21 03:50:01
表示想不到二分答案qwq
将树看作以陷阱为根。先考虑陷阱和起始点相邻的情况，此时老鼠一定会往下走，而如果管理者此时不做操作，那么一定会选择让操作次数变得最大的一棵子树。设\(f_i\)表示当前老鼠在第\(i\)个点、管理者先手，老鼠往下然后被逼回第\(i\)个点的最小操作次数。那么管理者一定会封掉儿子中\(f\)最大的，然后老鼠进入\(f\)次大的；当老鼠走到子树中一个点不能动的时候，管理者一定会把这个点的其他没有被封住的子树全部封住，这样显然是最优的。所以\(f_i = cmx\{f_j\} + du_i\)，那么相邻的情况答案就是\(f_m\)。
再考虑不相邻的情况，此时老鼠能够往上走，而往上走管理者可以选择把更高的地方向下的更优决策封住，或者把当前点向下的一个较优决策封住，这都是难以把控和简单地通过DP进行评估的。我们需要考虑一些不同的做法。
考虑一件事情，为什么我们不能够在老鼠往上走的时候得知管理者的操作，因为我们不知道是把当前的封住更优，还是上面有更优的决策。如果我们能够知道管理者应该封住的是答案大于多少的子树，那么就很好做了。注意到答案有二分性，于是考虑二分答案。
二分一个答案之后我们就只需要快速计算每一棵子树的答案。如果老鼠选择走进了这一棵子树，那么答案就是“这棵子树的DP值+当前点到根的所有点、不考虑向父亲的边的情况下的度数+1-[当前点不是起点]+从起点到这个点（不算这个点）封掉的子树个数”，+1是把当前向下的边清理，减的布尔变量表示向上过来的一条脏的边可以减少一次操作。如果当前点的子树中这样的子树数量很多以至于管理员用尽所有次数都封不完，那么当前答案可行；如果这样的子树数量大于等于二分值，那么也是可行的。
最新文章
- 局域网象棋游戏（C++实现，使用Socket，界面使用Win32，CodeBlocks+GCC编译）
- CodeForces 466E Information Graph --树形转线性+并查集
- .NET 相关工具
- Linux FTP配置文件说明
- centos到底下载哪个版本？
- css 包含的图片和style="display:none"可以避免图片加载，可以节省网络流量
- [Node.js] npm init && npm install
- 在Sublime Text 3中配置编译和运行C++程序
- javascript 中的location.reload
- HDU1257-最少拦截系统
- SharePoint 创建一个简单的Web Part 部分
- QuickTime视频解析问题
- homebrew 无法安装提示不能在根目录下使用
- 在Asp.Net Core中集成ABP Dapper
- Python网络编程基础pdf
- WGAN讲解
- 【Java】的四种引用的区别
- 指定分隔符连接数组元素join()
- PHP程序员职业发展路线
- 用python socket模块实现简单的文件下载