将$n$个长方形分成若干部分，每一部分的花费为部分中长方形的$max_长*max_宽$(不是$max_{长*宽}$)，求最小花费
首先，可以被其他长方形包含的长方形可以删去
然后我们按长方形的长度从小到大排序(排序后的长方形的宽度一定是从大到小)
设$f(i)$表示前i个长方形的最小花费，长方形的长和宽分别为$x(i),y(i)$，则有方程
$\Large f(i)=min(f(j)+x(i)*y(j+1))$
若对于某个$i$有$j$比$k$优,则
$f(j)+x(i)*y(j+1)\le f(k)+x(i)*y(k+1)$
化简得$\frac{f(j)-f(k)}{y(k+1)-y(j+1)}\le x(i)$
维护下凸壳即可
#include<cstdio> #include<algorithm> using namespace std; #define maxn 50005 #define LL long long struct Node{ int x,y; bool operator < (const Node& a)const{ return x!=a.x?x<a.x:y<a.y; } }a[maxn]; int n,si,que[maxn],s,t=1; LL f[maxn]; LL calc(int i,int j){ return (f[i]-f[j]-1)/(a[j+1].y-a[i+1].y)+1; } void insert(int x){ while(s<t-1&&calc(x,que[t-1])<=calc(que[t-1],que[t-2]))t--; que[t++]=x; } int main(){ scanf("%d",&n); for(int i=1;i<=n;i++){ scanf("%d%d",&a[i].x,&a[i].y); } sort(a+1,a+n+1); for(int i=1;i<=n;i++){ while(si&&a[si].y<=a[i].y)si--; a[++si]=a[i]; }n=si; for(int i=1;i<=n;i++){ while(s<t-1&&calc(que[s+1],que[s])<=a[i].x)s++; int w=que[s]; f[i]=f[w]+1ll*a[i].x*a[w+1].y; insert(i); } printf("%lld",f[n]); return 0; }
BZOJ1597: [Usaco2008 Mar]土地购买——斜率优化
原文：https://www.cnblogs.com/bennettz/p/9088883.html