题目列表

分别建立区间最小值和最大值 ST 表，让每次静态区间极差查询 O(1) 完成。

把超过目标重量的状态统一压到 dp[h]，用完全背包在 O(nh) 内求出达到至少 h 磅干草的最小花费。

枚举最后一个不选的断点，把 DP 转移化为窗口最大值并用单调队列维护。

把居住点建成完全图，按距离做 Kruskal 聚类，剩 k 个集合时的下一条跨集合边就是答案。

把已有道路先用并查集合并，再在所有点对构成的完全图上跑 Kruskal 求最小新增长度。