从洛谷P2900到YBT金牌导航土地购买这道DP神题我是如何用斜率优化啃下来的附完整代码第一次在洛谷刷到P2900这道题时我盯着土地购买的标题发了十分钟呆。题目描述看似简单给定n块土地的长和宽划分成若干组每组的花费是组内土地长的最大值乘以宽的最大值求最小总花费。但当我尝试用常规动态规划思路时很快发现O(n²)的朴素DP在n5e4的数据范围下根本行不通。这道题就像一堵高墙让我这个刚学斜率优化的菜鸟望而生畏。1. 理解题意与贪心预处理1.1 问题本质的挖掘最初我误以为这是个简单的分组问题直到画出几个测试用例才恍然大悟。考虑三块土地A(10,1)、B(5,5)、C(1,10)如果单独分组总花费是10×1 5×5 1×10 45而将B和C分在一组则是10×1 5×10 60——这显然更差。但把A和B分一组呢(10×5) (1×10) 60依然不理想。这个简单的例子让我意识到关键观察1当一块土地的长和宽都小于另一块时它可能成为免费搭车的对象关键观察2最优分组往往与土地的长宽相对大小有关1.2 贪心预处理的突破参考YBT金牌导航的讨论区我发现了预处理的关键步骤按长降序、宽升序排序这步操作让后续处理变得直观去除冗余土地对于排序后的土地序列如果某块土地的宽不大于前面所有土地的宽最大值它就可以被安全移除struct node { int x, y; }a[50001], p[50001]; bool cmp(node x, node y) { if (x.x ! y.x) return x.x y.x; return x.y y.y; } // 预处理去除冗余土地 n 1; p[n] a[1]; maxn a[1].y; for (int i 2; i nn; i) if (a[i].y maxn) { p[n] a[i]; maxn a[i].y; }这个预处理将问题转化为在长递减、宽递增的土地序列中找到最优的分割点序列。此时每组的花费就是该组第一块土地的长乘以最后一块土地的宽。2. 动态规划模型建立2.1 朴素DP方程的构建经过预处理后设f[i]表示前i块土地的最小花费可以得到转移方程f[i] min{f[j] p[j1].x * p[i].y} for 0 ≤ j i这个方程的含义是将j1到i的土地分为一组花费是该组长最大值p[j1].x乘以宽最大值p[i].y。我最初用这个方程写了个O(n²)的DP在n5000时还能勉强通过但面对5e4的数据就彻底超时了。2.2 四边形不等式与决策单调性在卡了三天后我偶然看到洛谷讨论区提到四边形不等式和决策单调性。经过验证费用函数w(j,i) p[j1].x * p[i].y满足四边形不等式决策点具有单调性设k[i]是f[i]的最优决策点那么k[i] ≤ k[i1]这意味着我们可以使用决策单调性优化将复杂度从O(n²)降到O(nlogn)。3. 斜率优化实现细节3.1 决策队列的维护实现斜率优化的核心是维护一个可能成为最优决策点的队列。每个决策点j对应一个转移区间[l,r]表示在这个区间内j是最优决策。top 1; low 1; sta[1] 0; l[1] 0; r[1] n; for (int i 1; i n; i) { if (l[low] r[low]) l[low]; else low; f[i] clac(sta[low], i); // 新决策i的评估 if (clac(i, n) clac(sta[top], n)) continue; // 维护队列单调性 while (low top clac(i, l[top]) clac(sta[top], l[top])) top--; if (low top) { top; sta[top] i; l[top] i; r[top] n; continue; } // 二分查找分割点 int lef l[top], rig r[top], re; while (lef rig) { int mid (lef rig) 1; if (clac(i, mid) clac(sta[top], mid)) { re mid; rig mid - 1; } else lef mid 1; } r[top] re - 1; top; sta[top] i; l[top] re; r[top] n; }3.2 调试中的关键发现在实现过程中我遇到了几个坑点初始边界处理需要将0作为初始决策点加入队列二分查找条件必须严格判断clac(i,mid) ≤ clac(sta[top],mid)队列维护顺序先处理过期决策再评估新决策4. 完整代码与性能分析最终AC的完整代码如下在洛谷上运行时间100ms#includecstdio #includealgorithm using namespace std; struct node { int x, y; }a[50001], p[50001]; int n, nn, sta[50001], l[50001], top, low, r[50001], maxn; long long f[50001]; bool cmp(node x, node y) { if (x.x ! y.x) return x.x y.x; return x.y y.y; } long long clac(int x, int y) { return f[x] 1ll * p[x 1].x * p[y].y; } int main() { scanf(%d, nn); for (int i 1; i nn; i) scanf(%d %d, a[i].x, a[i].y); sort(a 1, a nn 1, cmp); n 1; p[n] a[1]; maxn a[1].y; for (int i 2; i nn; i) if (a[i].y maxn) { p[n] a[i]; maxn a[i].y; } top 1; low 1; sta[1] 0; l[1] 0; r[1] n; for (int i 1; i n; i) { if (l[low] r[low]) l[low]; else low; f[i] clac(sta[low], i); if (clac(i, n) clac(sta[top], n)) continue; while (low top clac(i, l[top]) clac(sta[top], l[top])) top--; if (low top) { top; sta[top] i; l[top] i; r[top] n; continue; } int lef l[top], rig r[top], re; while (lef rig) { int mid (lef rig) 1; if (clac(i, mid) clac(sta[top], mid)) { re mid; rig mid - 1; } else lef mid 1; } r[top] re - 1; top; sta[top] i; l[top] re; r[top] n; } printf(%lld, f[n]); return 0; }4.1 复杂度分析预处理阶段排序O(nlogn)去冗余O(n)DP阶段每个决策点最多入队出队一次每次二分O(logn)总复杂度O(nlogn)4.2 替代方案比较除了决策单调性这道题还可以用斜率优化实现方法时间复杂度实现难度适用性朴素DPO(n²)简单小数据量决策单调性O(nlogn)中等通用斜率优化O(n)较难特定条件在实际项目中我后来用斜率优化重新实现了这道题发现代码更简洁但理解门槛更高。对于初学者建议先从决策单调性入手。