http://www.lydsy.com/JudgeOnline/problem.php?id=1597
https://www.luogu.org/problemnew/show/P2900
约翰准备扩大他的农场，眼前他正在考虑购买N块长方形的土地。如果约翰单买一块土 地，价格就是土地的面积。但他可以选择并购一组土地，并购的价格为这些土地中最大的长 乘以最大的宽。比如约翰并购一块3 × 5和一块5 × 3的土地，他只需要支付5 × 5 = 25元， 比单买合算。 约翰希望买下所有的土地。他发现，将这些土地分成不同的小组来并购可以节省经费。 给定每份土地的尺寸，请你帮助他计算购买所有土地所需的最小费用。
为了写模拟赛的代码现学了斜率优化。
我们显然对于所有的土地按照长宽为第一、第二关键字降序排序，这样的话我们发现对于一块土地，要么它和它前面的土地捆绑买，要么和它后面的土地捆绑买，除此之外的买法显然不优。
那这样我们显然有一个O(n^2)的转移，接下来我们考虑优化。
我们要想优化dp，显然要有单调性，考虑到当一块土地的l和w都小于其它一些土地时它只能被捆绑买且对答案没有贡献，那么我们就可以删掉这些点。
那么剩下的点显然满足l单调降w单调升，于是先列出转移方程f[i]=min(f[k]+l[k+1]*w[i])。
考虑当k<j<i时，如果f[k]+l[k+1]*w[i]>f[j]+l[j+1]*w[i]，那么显然j的状态是更优的，我们就可以把小的k踢出去。
将该式子可化为g[k,j]=(f[k]-f[j])/(l[j+1]-l[k+1])>w[i]，于是我们有了一种判断当前状态是否需要被踢出的方法。
那么我们开一个单调队列，它的头就可以用这个方式维护。
至于它的尾，考虑当k<j<i时我们可以通过g[k,j]<g[j,i]来踢出j。
为什么？考虑如果g[j,i]>w我们就可以把j踢出。
如果g[k,j]<g[j,i]<w时那么显然k比j优，所以我们还可以把j踢出。
于是我们就能处理尾部了。
那么剩下的就很显然了，只有头指针代表的元素才是最优的，那么只从头处转移即可。
#include<iostream> #include<cstring> #include<cstdio> #include<cmath> #include<algorithm> using namespace std; typedef long long ll; const int N=50010; inline int read(){ int X=0,w=1;char ch=0; while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();} while(ch>='0'&&ch<='9')X=(X<<1)+(X<<3)+ch-'0',ch=getchar(); return X*w; } struct buy{ ll l,w; }a[N],b[N]; bool cmp(buy a,buy b){ return a.l>b.l||(a.l==b.l&&a.w>b.w); } int n,cnt,l,r,maxw; ll f[N],q[N]; inline double suan(int j,int k){ return 1.0*(f[j]-f[k])/(b[k+1].l-b[j+1].l); } int main(){ n=read(); for(int i=1;i<=n;i++) a[i].l=read(),a[i].w=read(); sort(a+1,a+n+1,cmp); for(int i=1;i<=n;i++){ if(a[i].w>maxw){ maxw=a[i].w; b[++cnt]=a[i]; } } for(int i=1;i<=cnt;i++){ while(l<r&&suan(q[l],q[l+1])<(double)b[i].w)l++; f[i]=f[q[l]]+b[q[l]+1].l*b[i].w; while(l<r&&suan(q[r],i)<suan(q[r-1],q[r]))r--; q[++r]=i; } printf("%lld ",f[cnt]); return 0; }
+++++++++++++++++++++++++++++++++++++++++++
+本文作者：luyouqi233。 +
+欢迎访问我的博客：http://www.cnblogs.com/luyouqi233/+
+++++++++++++++++++++++++++++++++++++++++++