从洛谷P2900到斜率优化：土地购买问题的保姆级DP推导与代码实现

从洛谷P2900到斜率优化土地购买问题的保姆级DP推导与代码实现在算法竞赛中动态规划(DP)优化技巧一直是区分选手水平的重要分水岭。今天我们要深入探讨的这道题目——洛谷P2900土地购买问题恰好为我们提供了一个绝佳的学习案例。这道题不仅考察基础DP建模能力更要求我们掌握斜率优化这一进阶技巧。让我们从零开始一步步拆解这道经典题目。1. 问题理解与贪心预处理土地购买问题的核心在于如何高效分组。题目给出n块土地每块土地有长(x)和宽(y)两个属性。我们可以将土地分成任意组每组的花费是该组中土地的最大长度乘以最大宽度。我们的目标是找到总花费最小的分组方案。贪心预处理的必要性直接对所有土地进行DP处理会导致复杂度爆炸存在一些土地对最终解完全没有贡献通过排序可以简化后续DP状态转移具体预处理步骤将所有土地按长度从大到小排序长度相同则按宽度从大到小排序遍历排序后的土地保留那些宽度大于之前所有土地宽度的土地struct Land { int x, y; }; bool compare(const Land a, const Land b) { return a.x ! b.x ? a.x b.x : a.y b.y; } vectorLand preprocess(vectorLand lands) { sort(lands.begin(), lands.end(), compare); vectorLand valid; int max_y 0; for (auto land : lands) { if (land.y max_y) { valid.push_back(land); max_y land.y; } } return valid; }经过预处理后我们得到的新土地序列满足长度严格递减宽度严格递增这个性质对后续的DP优化至关重要。2. 基础DP模型构建有了预处理后的土地序列我们可以建立基础DP模型。设f[i]表示购买前i块土地的最小花费。状态转移方程f[i] min(f[j] cost(j1, i)) for 0 ≤ j i其中cost(j1, i) x[j1] * y[i]因为预处理后x递减y递增这个转移方程的时间复杂度是O(n²)对于n5×10⁴的数据量显然无法承受。关键观察预处理后的土地序列具有单调性这提示我们可能可以使用决策单调性优化进一步分析可以发现满足四边形不等式条件3. 斜率优化与决策单调性斜率优化的核心思想是将转移方程转化为几何问题。让我们重新整理状态转移方程f[i] min(f[j] x[j1] * y[i])可以将其改写为f[i] y[i] * x[j1] f[j]这类似于直线方程y kx b其中k y[i]x x[j1]b f[j]我们需要找到使这个表达式最小的j。这相当于在一系列直线中在x y[i]处找到最低的点。决策单调性的证明定义决策点j优于k的条件证明对于ii如果j优于k那么j仍然优于k这保证了决策点的单调递增性具体证明过程需要分析交叉点位置的变化这里我们关注实现方法。4. 二分队列实现斜率优化斜率优化的经典实现方式是维护一个决策队列其中每个决策都优于后面的决策。对于每个i我们移除队首已经不如后续决策优的决策用队首决策计算f[i]将i作为新决策加入队尾维护队列的斜率单调性typedef long long ll; struct Decision { int j; // 决策点 int l, r; // 有效区间 }; ll compute(int j, int i, const vectorLand lands) { return f[j] (ll)lands[j1].x * lands[i].y; } ll solve(const vectorLand lands) { int n lands.size(); vectorll f(n1); dequeDecision q; // 初始决策不选任何土地 q.push_back({0, 1, n}); f[0] 0; for (int i 1; i n; i) { // 弹出过期的决策 while (!q.empty() q.front().r i) q.pop_front(); if (!q.empty()) q.front().l i; // 计算f[i] int best_j q.front().j; f[i] compute(best_j, i, lands); // 尝试将i加入决策队列 while (!q.empty()) { Decision last q.back(); if (compute(i, last.l, lands) compute(last.j, last.l, lands)) { break; } q.pop_back(); } if (q.empty()) { q.push_back({i, i1, n}); } else { Decision last q.back(); int low last.l, high last.r, pos n1; while (low high) { int mid (low high) / 2; if (compute(i, mid, lands) compute(last.j, mid, lands)) { pos mid; high mid - 1; } else { low mid 1; } } if (pos n) { q.back().r pos - 1; q.push_back({i, pos, n}); } } } return f[n]; }5. 完整代码实现与测试将上述各部分组合起来我们得到完整的解决方案#include iostream #include vector #include algorithm #include deque using namespace std; struct Land { int x, y; bool operator(const Land other) const { return x ! other.x ? x other.x : y other.y; } }; vectorLand preprocess(vectorLand lands) { sort(lands.begin(), lands.end()); vectorLand valid; int max_y 0; for (auto land : lands) { if (land.y max_y) { valid.push_back(land); max_y land.y; } } return valid; } typedef long long ll; ll solve(const vectorLand lands) { int n lands.size(); vectorll f(n1); struct Decision { int j, l, r; }; dequeDecision q; q.push_back({0, 1, n}); f[0] 0; auto compute [](int j, int i) { return f[j] (ll)lands[j].x * lands[i-1].y; }; for (int i 1; i n; i) { while (!q.empty() q.front().r i) q.pop_front(); if (!q.empty()) q.front().l i; int best_j q.front().j; f[i] compute(best_j, i); while (!q.empty()) { auto last q.back(); if (compute(i, last.l) compute(last.j, last.l)) break; q.pop_back(); } if (q.empty()) { q.push_back({i, i1, n}); } else { auto last q.back(); int low last.l, high last.r, pos n1; while (low high) { int mid (low high) / 2; if (compute(i, mid) compute(last.j, mid)) { pos mid; high mid - 1; } else { low mid 1; } } if (pos n) { q.back().r pos - 1; q.push_back({i, pos, n}); } } } return f[n]; } int main() { int n; cin n; vectorLand lands(n); for (int i 0; i n; i) { cin lands[i].x lands[i].y; } vectorLand valid preprocess(lands); cout solve(valid) endl; return 0; }测试用例分析输入 4 100 1 15 15 20 5 1 100 预处理后保留的土地 (100,1), (20,5), (15,15), (1,100) 最优分组 (100,1)和(20,5)一组花费100*5500 (15,15)一组花费15*15225 (1,100)一组花费1*100100 总花费5002251008256. 算法复杂度与优化分析让我们分析这个解决方案的时间和空间复杂度时间复杂度预处理排序O(n log n)贪心筛选O(n)斜率优化DP每个决策最多入队出队一次O(n)每次二分查找O(log n)总复杂度O(n log n)空间复杂度存储土地数据O(n)DP数组O(n)决策队列O(n)总空间O(n)优化技巧总结贪心预处理通过排序和筛选去除无效土地简化问题决策单调性利用土地序列的单调性质证明四边形不等式斜率优化将转移方程转化为几何问题使用单调队列维护二分查找快速确定新决策的有效区间在实际比赛中这类问题的难点往往在于识别出可以使用斜率优化的场景正确推导和证明决策单调性准确实现二分队列的逻辑7. 常见错误与调试技巧在实现斜率优化时容易犯以下错误预处理错误排序方式不正确没有正确筛选掉被支配的土地转移方程错误混淆x和y的顺序没有正确处理边界条件(j0)斜率优化实现错误队列维护逻辑错误二分查找条件写反没有正确处理决策点的有效区间调试建议先在小数据集上验证预处理结果打印中间决策队列的状态对比朴素DP和优化DP的结果使用assert检查关键不变量// 调试打印决策队列 void print_queue(const dequeDecision q, const vectorll f, const vectorLand lands) { cout Decision Queue: endl; for (auto d : q) { cout j d.j [ d.l , d.r ] ; cout f f[d.j] x lands[d.j].x; cout endl; } }8. 扩展与应用斜率优化不仅适用于土地购买问题还可以解决许多类似的最优化问题。常见的应用场景包括任务调度问题将任务分组执行每组有启动成本和执行成本生产批次问题决定生产批次大小平衡库存成本和启动成本投资组合优化选择投资组合平衡风险和收益识别斜率优化适用性的特征状态转移方程可以表示为min/max(线性函数)决策变量具有单调性代价函数满足四边形不等式在实际应用中我们可以通过以下步骤来解决问题建立基础DP模型尝试简化或预处理输入数据分析状态转移方程的性质确定适用的优化技术实现并验证优化后的算法土地购买问题为我们提供了一个很好的学习案例展示了如何将看似复杂的问题通过逐步分析和优化最终得到一个高效的解决方案。掌握这些技巧后你就能在算法竞赛中更从容地应对类似的DP优化问题。