Description：

有 $ n $ 块长方形的土地，你每次可以买很多块土地，花的价格是这些土地中长的最大值乘以宽的最大值，买的次数没有限制。问把所有土地都买完的最小花费。

$1\le n \le 5\times 10^4$

Solution：

最大值很不好操作，发现如果有一个矩形长和宽都比另一个矩形大，那么那个小矩形是没用的，于是先把所有矩形按长排序，把包含的矩形都去掉，然后发现一次一定买一段，因为买一段的价值为第一块的长 $\times$ 最后一块的宽，于是如果嵌套着买的话一定不优，所以一定每次买一段。

$DP$ 方程为 $f[i]=min(f[j]+w[j+1] \times h[i])$ ，显然是可以斜率优化的，化一下得： $-f[j]=h[i]\times w[j+1]-f[i]$ ，斜率为正且单调递增，点的横坐标单调递减，使截距尽量大，可以用单调队列维护上凸壳。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cstring>

using namespace std;

int m;

#define MAXN 50010

typedef long long ll;

struct land

{

	ll w,h;

}l[MAXN],d[MAXN];

bool cmp(land x,land y){return (x.h == y.h ? x.w < y.w : x.h < y.h);}

bool cmp2(land x,land y){return x.h < y.h;}

int q[MAXN],head = 1,tail = 0;

long long f[MAXN];

double slope(int a,int b)

{

	return (double)(-f[a] - (-f[b])) / (double)(d[a + 1].w - d[b + 1].w);

}

int main()

{

	scanf("%d",&m);

	for(int i = 1;i <= m;++i)

	{

		scanf("%lld%lld",&l[i].w,&l[i].h);

	}

	sort(l + 1,l + 1 + m,cmp);

	ll maxw = 0;

	int n;

	for(int i = m;i >= 1;--i)

	{

		if(l[i].w > maxw)

		{

			d[++n] = l[i];

			maxw = l[i].w;

		}

	}

	sort(d + 1,d + 1 + n,cmp2);

	memset(f,0xc0,sizeof(f));

	f[0] = 0;

	q[++tail] = 0;

	for(int i = 1;i <= n;++i)

	{

		while(head < tail && (double)d[i].h > slope(q[head],q[head + 1]))++head;

		f[i] = f[q[head]] + d[q[head] + 1].w * d[i].h;

		while(head < tail && slope(q[tail],i) < slope(q[tail - 1],q[tail]))--tail;

		q[++tail] = i;

	}

	cout << f[n] << endl;

	return 0;

}