题目
题目链接：http://www.lydsy.com/JudgeOnline/problem.php?id=1597
农夫John准备扩大他的农场，他正在考虑 \(N\) 块长方形的土地。每块土地的价格是它的面积，但FJ可以同时购买多快土地。 这些土地的价格是它们最大的长乘以它们最大的宽, 但是土地的长宽不能交换。 如果FJ买一块 \(3\times 5\) 的地和一块 \(5\times 3\) 的地，则他需要付 \(5\times 5=25\)。FJ希望买下所有的土地，但是他发现分组来买这些土地可以节省经费。 他需要你帮助他找到最小的经费。
思路
经典的斜率优化题。基本上会板子就可以做出来吧（
如果两块土地分别为 \(a_i\times b_i\) 和 \(a_j\times b_j\)，且满足 \(a_i\geq a_j,b_i\geq b_j\)，那么显然把这两块土地划进一个集合里会最优。因为其中一块土地不会产生代价。换句话说，如果一块土地 \(i\) 会被其他土地完全包含，那么 \(i\) 是不会对答案有贡献的。
那么将完全包含的土地剔除后，将剩余土地按长从小到大排序，那么宽一定是严格降序的。那么为了最优，显然应该划分成若干连续的区间。同时如果将 \([i,j]\) 划分成一个集合，那么产生的代价是 \(a_j\times b_i\)。
所以设前 \(i\) 片土地全部买下来所需最小代价为 \(f[i]\)，则有
\[f[i]=\min(f[j]+a_i\times b_{j+1})
\]
化简成 \(f[j]=-a_i\times b_{j+1}+f[i]\)，那么每一个决策点对应的就是 \((-b_{j+1},f_j)\)。由于 \(a_i\) 满足单调性，所以单调队列维护下凸壳即可。
时间复杂度 \(O(n)\)。
代码
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
const int N=50010,M=1000010;
int n,m,a[N],b[N],q[N];
ll f[N];
struct node
{
int a,b;
bool flag;
}c[N];
bool cmp(node x,node y)
{
if (x.a<y.a) return 1;
if (x.a>y.a) return 0;
return x.b<y.b;
}
int main()
{
scanf("%d",&m);
for (int i=1;i<=m;i++)
scanf("%d%d",&c[i].a,&c[i].b);
sort(c+1,c+1+m,cmp);
for (int i=m,maxn=0;i>=1;i--)
if (c[i].b<=maxn) c[i].flag=1;
else maxn=c[i].b;
for (int i=1;i<=m;i++)
if (!c[i].flag)
{
n++;
a[n]=c[i].a; b[n]=c[i].b;
}
int l=1,r=1;
for (int i=1;i<=n;i++)
{
for (int x=q[l],y=q[l+1];l<r;x=q[l],y=q[l+1])
if (l<r && f[y]-f[x]<=1LL*a[i]*(b[x+1]-b[y+1])) l++;
else break;
f[i]=f[q[l]]+1LL*a[i]*b[q[l]+1];
for (int x=q[r-1],y=q[r];l<r;x=q[r-1],y=q[r])
if (l<r && (f[y]-f[x])*(b[y+1]-b[i+1])>=(f[i]-f[y])*(b[x+1]-b[y+1])) r--;
else break;
q[++r]=i;
}
printf("%lld",f[n]);
return 0;
}
/*
4
100 1
15 15
20 5
1 100
*/