CDQ分治包含示例货币兑换与偏序问题

最近在归档一些早期的资料，在某个偶然间回忆起了自己曾经参与过OI项目时学到的一些CDQ分治的知识，并希望通过分享的方式与大家探讨这一部分内容

目录

预备知识

常见递归复杂度

分治思想

CDQ分治例题

货币兑换

PARTIAL ORDER

问题2D版本

问题3D版本

问题4D简化版本

问题4D版本

问题100D版本

总结

题目推荐

---

CDQ分治是一种高级的分治方法，在OI领域首次提出于陈丹琦2008年国家集训队作业中。

预备知识

常见递归复杂度

先来分析下面这个递归方程：

其时间复杂度如何分析？

将式子迭代两次得：

继续迭代，整理得：