本文主要是介绍[Usaco2008 Mar]土地购买 斜率优化的DP，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
农夫John准备扩大他的农场,他正在考虑N (1 <= N <= 50,000) 块长方形的土地. 每块土 地的长宽满足(1 <= 宽 <= 1,000,000; 1 <= 长 <= 1,000,000). 每块土地的价格是它的面积,但FJ可以同时购买多快土地. 这些土地的价格是它们最大的长乘以 它们最大的宽, 但是土地的长宽不能交换. 如果FJ买一块3x5的地和一块5x3的地,则他需要 付5x5=25. FJ希望买下所有的土地,但是他发现分组来买这些土地可以节省经费. 他需要你帮助他找到最小 的经费.
这题还算是比较经典的。
首先我们按x,y都递减排序。其中x是宽，y是长
然后发现如果一个矩形的长宽都不大于另一个矩形的长宽。那么这个矩形的花费就是0，因为买那个矩形顺便就买了这个小的。
所以去除这些不花钱的矩形。
剩下的矩形，x是递减的，y是递增的
然后可以写出转移方程
f[i] = min(f[j] + x[j + 1] * y[i]) (j < i)
然后为了方便，把x数组坐标提前一下
f[i] = min(f[j] + x[j] * y[i]) (j < i)
然后发现是n ^2的。不优化会超时
这就要用到经典的斜率优化了
考虑两个决策f[j],f[k]并假设j<k。
如果对于f[i]，从f[j]转移来比从f[k]转移来更优，那么有：
f[j]+x[j]*y[i]<f[k]+x[k]*y[i]
移项得：
y[i]<(f[k]-f
这篇关于[Usaco2008 Mar]土地购买 斜率优化的DP的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
