标签:分治
3 个条目
-
概念 分治优化决策单调DP
当 Q_(i,j) (f(j))=w(i,j) 与 f(j) 无关且最优决策点满足决策单调性时,按中点扫描候选区间并递归,以 O(n log n) 求出全部 f(i)。
2026-11-13 -
二维 Delaunay 三角剖分的分治构造:按 x 分治,递归构造两侧后合并上下公切线之间的跨边,O(n log n)。
2026-11-10 -
题目 最小差值生成树
边权极差最小的生成树;排序后滑窗得到加删边区间,二分答案并用时间分治与可撤销并查集判定。
2026-11-10