本文主要是介绍bzoj1597: [Usaco2008 Mar]土地购买，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
1597: [Usaco2008 Mar]土地购买
Time Limit: 10 Sec Memory Limit: 162 MB
Description
农夫John准备扩大他的农场,他正在考虑N (1 <= N <= 50,000) 块长方形的土地. 每块土地的长宽满足(1 <= 宽 <= 1,000,000; 1 <= 长 <= 1,000,000). 每块土地的价格是它的面积,但FJ可以同时购买多快土地. 这些土地的价格是它们最大的长乘以它们最大的宽, 但是土地的长宽不能交换. 如果FJ买一块3x5的地和一块5x3的地,则他需要付5x5=25. FJ希望买下所有的土地,但是他发现分组来买这些土地可以节省经费. 他需要你帮助他找到最小的经费.
Input
第1行: 一个数: N
第2..N+1行: 第i+1行包含两个数,分别为第i块土地的长和宽
Output
- 第一行: 最小的可行费用.
Sample Input
4
100 1
15 15
20 5
1 100
输入解释:
共有4块土地.
Sample Output
500
HINT
FJ分3组买这些土地: 第一组:100x1, 第二组1x100, 第三组20x5 和 15x15 plot. 每组的价格分别为100,100,300, 总共500.
Source
Gold
分析
这题还是挺有意思的。
首先，这一题涉及分组和max有关的运算，这提示我们可以试试排序后进行划分dp。
那么我们将所有的矩形按长递增进行排序。
然后我们发现，对于2个矩形x和y，如果x的长小于等于y的长，且x的宽小于等于y的宽。
那么如果将x和y分在一组，那么购买x肯定是不需要花费额外代价的(x会被其他的矩形完全包含)。
那么我们就可以将x这个矩形扔掉。
因此我们可以在排序(时间复杂度O(nlog n))之后，我们就可以剔除掉所有没有用的矩形。显然剔除掉所有没有用的矩形后，矩形数组中长是递增的，宽是递减的。因此我们可以利用一个单调栈完成剔除操作，时间复杂度O(n)。
进行了这些预处理后，数组具有了单调性，我们也就可以顺利写出dp方程了
记f[i]为前i个矩形的最小代价，a[i]为第i个矩形的长，b[i]为第i个矩形的宽，那么
f[i]=min{f[j-1]+a[i]*b[j]}
接着就是对方程式变形，最终得到
(f[j-1]-f[k-1])/(b[j]-b[k])>-a[i]时 k优于j
那么就可以使用斜率优化了
算法的总时间复杂度为O(nlog n)，空间复杂度为O(n)
这篇关于bzoj1597: [Usaco2008 Mar]土地购买的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
