【树形DP】CF1016F Road Projects
2021/10/26 23:09:29
本文主要是介绍【树形DP】CF1016F Road Projects,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
传送门
题解
一开始想的是先求出 \(1,n\) 的单源最短路,之后枚举中转点把两段拼起来,几乎写完了之后才发现我这个想法根本就不对。(因为没办法简单地把两段路径拼在一起)重构了,用时巨长。
其实,按照上面的思路继续,应该也不难想出正解。
变换一下视角,把 \(1 - n\) 的路径单独提出来,以后的操作基于这条链。
这条链上可能挂着一些子树,分类讨论。
- 如果有大小超过 \(2\) 的子树(包括链上的那个点),就可以在子树内连边,不对答案造成影响。
- 如果没有上述子树,说明链上顶多有一条边伸出去。此时继续分类讨论。
- 对于每一个链上的点,都可以隔一个链上相邻的点连边。(按照贪心,不会隔着更多的点连边)
- 对于每一个伸出去的点,都可以和链上相邻的两点连边。同时,也可以和前面其他伸出去的点连边。
细节略多,如果考试的话我八成写挂了吧...现在要细节再细节...
代码
这篇关于【树形DP】CF1016F Road Projects的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-12-25安卓NDK 是什么?-icode9专业技术文章分享
- 2024-12-25caddy 可以定义日志到 文件吗?-icode9专业技术文章分享
- 2024-12-25wordfence如何设置密码规则?-icode9专业技术文章分享
- 2024-12-25有哪些方法可以实现 DLL 文件路径的管理?-icode9专业技术文章分享
- 2024-12-25错误信息 "At least one element in the source array could not be cast down to the destination array-icode9专业技术文章分享
- 2024-12-25'flutter' 不是内部或外部命令,也不是可运行的程序 或批处理文件。错误信息提示什么意思?-icode9专业技术文章分享
- 2024-12-25flutter项目 as提示Cannot resolve symbol 'embedding'提示什么意思?-icode9专业技术文章分享
- 2024-12-24怎么切换 Git 项目的远程仓库地址?-icode9专业技术文章分享
- 2024-12-24怎么更改 Git 远程仓库的名称?-icode9专业技术文章分享
- 2024-12-24更改 Git 本地分支关联的远程分支是什么命令?-icode9专业技术文章分享