题目链接：http://www.lydsy.com/JudgeOnline/problem.php?id=1597
题意：
有n块矩形土地，长为a[i]，宽为b[i]。
FJ想要将这n块土地全部买下来。
土地可以分组购买。
若有某一些土地被分到了一组，则将这一组土地全部买下的花费为他们的max(a[i])*max(b[i])。
问你最小总花费是多少。
题解：
首先，如果一块土地能够被另一块土地完全包含（即长宽都比另一个小），那么被包含的那块土地可以忽略不计。
然后贪心地考虑如何使花费最小：
如果要使花费尽可能小，则分在同一组中矩形的长宽差距应尽可能地小。
所以将长a[i]作为第一关键字，将宽b[i]作为第二关键字排序。
此时矩形的长a[i]一定是非降的，那么对于两个矩形i和j(i<j)，如果有b[i]<=b[j]，则j一定能完全包含i。
利用这一特性将所有能被包含的矩形去掉。
此时矩形的宽b[i]就变成了严格递减的了。
显然，此时分到一组中的矩形必须是连续的一段区间，才有可能最优。
然后就可以dp了。
表示状态：
dp[i]表示已经购买了前i块土地的最小花费。
找出答案：
假设去掉能被包含的矩形之后，矩形总数为tot。
ans = dp[tot]
如何转移：
dp[i] = min dp[j] + a[i]*b[j+1]
边界条件：
dp[0] = 0
斜率优化：
设j < k，且k的决策更优。
则：dp[j] + a[i]*b[j+1] > dp[k] + a[i]*b[k+1]
整理得：(dp[k]-dp[j])/(b[j+1]-b[k+1]) < a[i]
所以slope(i,j) = (dp[i]-dp[j])/(b[j+1]-b[i+1])
由于a[i]非降，所以用单调队列维护下凸壳即可。
AC Code:
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>
#define MAX_N 50005 using namespace std; struct Rect
{
long long a,b;
Rect(long long _a,long long _b)
{
a=_a; b=_b;
}
Rect(){}
friend bool operator < (const Rect &x,const Rect &y)
{
return x.a!=y.a ? x.a<y.a : x.b<y.b;
}
}; int n;
int q[MAX_N];
long long dp[MAX_N];
Rect x[MAX_N]; void read()
{
cin>>n;
for(int i=;i<=n;i++)
{
cin>>x[i].a>>x[i].b;
}
} inline double slope(int i,int j)
{
return (double)(dp[i]-dp[j])/(x[j+].b-x[i+].b);
} void work()
{
sort(x+,x++n);
int tot=;
for(int i=;i<=n;i++)
{
while(tot && x[i].b>=x[tot].b) tot--;
x[++tot]=x[i];
}
x[tot+]=Rect(,);
int l=,r=;
q[]=,dp[]=;
for(int i=;i<=tot;i++)
{
while(l<r && slope(q[l],q[l+])<=x[i].a) l++;
dp[i]=dp[q[l]]+x[i].a*x[q[l]+].b;
while(l<r && slope(q[r],i)<slope(q[r-],q[r])) r--;
q[++r]=i;
}
cout<<dp[tot]<<endl;
} int main()
{
read();
work();
}