[bzoj 1597] [Usaco2008 Mar]土地购买

Description

农夫John准备扩大他的农场,他正在考虑N (1 <= N <= 50,000) 块长方形的土地. 每块土地的长宽满足(1 <= 宽 <= 1,000,000; 1 <= 长 <= 1,000,000). 每块土地的价格是它的面积,但FJ可以同时购买多快土地. 这些土地的价格是它们最大的长乘以它们最大的宽, 但是土地的长宽不能交换. 如果FJ买一块3×5的地和一块5×3的地,则他需要付5×5=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组买这些土地: 第一组:100×1, 第二组1×100, 第三组20×5 和 15×15 plot. 每组的价格分别为100,100,300, 总共500.

不同与前面的两道题,这道题需要进行一些预处理以维护单调性.我们需要维护x单调递增且y单调递减,这样我们才能方便找到一段区间内的费用.(x递减,y递增也可以).然后我们就可以轻松地写出dp方程:f[i]=min{f[j]+x[i]*y[j+1]} (j<i)
然后我们用之前的方法去对这个式子变形就可以套上斜率优化了,这里我就不写上来了,式子比较好推.不过这里的一个亮点就是如何维护x递增,y递减.
首先如果存在两个矩形,其中一个矩形的长宽都要比另一个矩形的长宽要大,那么我们很容易发现,这个矩形对答案的贡献是完全没有的.那么我们可以去除掉这些被覆盖的矩形.我们先对以x为第一关键字排序,然后建立一个队列,从1-n枚举每一个矩形,然后由于x是递增的,那么我们就只要找到队列里面第一个y大于这一个矩形的就可以了.最后再把它放入队列里面.之后这个队列的元素就是我们要得到的元素了.因为x是单调递增的,要使得矩形不互相覆盖,只有y单调递减才可以.

#include <cstdio>
#include <algorithm>

using std:: max;
using std:: min;

typedef long long LL;

static const int maxm=1e6+10;

struct mtx{
	LL x,y;
	bool operator < (const mtx &m) const {
		return x==m.x?y<m.y:x<m.x;
	}
}A[maxm];

LL Q[maxm],xx[maxm],yy[maxm],f[maxm];
int cnt,n,head=1,tail=1;

double slp(int j,int k){
	return (double)(f[k]-f[j])/(yy[j+1]-yy[k+1]);
}

int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
		scanf("%lld%lld",&A[i].x,&A[i].y);
	
	std::sort(A+1,A+n+1);
	
	for(int i=1;i<=n;i++){
		while(cnt&&yy[cnt]<=A[i].y)cnt--;
		yy[++cnt]=A[i].y;xx[cnt]=A[i].x;
	}
	
	for(int i=1;i<=cnt;i++){
        while(head<tail&&slp(Q[head+1],Q[head])<=xx[i])head++;
        f[i]=f[Q[head]]+yy[Q[head]+1]*xx[i];
        while(head<tail&&slp(i,Q[tail])<=slp(Q[tail],Q[tail-1]))tail--;
        Q[++tail]=i;
    }
	
	printf("%lld\n",f[cnt]);
	
	return 0;
}

传送门