题目链接：P2900 [USACO08MAR] Land Acquisition G
我们通过题目可以得出一个较为清晰的结论：
- 我们将所有的矩形排列起来，可以发现最后被完全包含在另一个矩形内的矩形是没有意义的。
- 这样的话我们得到的所有矩形的并是呈阶梯状的，如下图：
- 其中，中间的浅蓝色的边是没有意义的
然后我们可以推导出一个 DP 式子：
我们设 \(f_{i}\) 表示购买前 \(i\) 个矩形的最小代价，那么我们可以得到：
\[f_i = \min_{j=1}^n\{f_{j-1}+l_j\times w_i\}
\]
化成斜率优化式子：
\[f_{j-1} = l_j \times (-w_i) + f_i
\]
我们要让 \(f_i\) 最小，那么就维护一个上凸包即可。
code:
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int NN = 5e4 + 8;
int n;
bool vis[NN];
int que[NN],head,tail;
ll f[NN];
struct Area{
int w,l;
bool operator < (const Area &x)const{
if(w == x.w) return l < x.l;
return w < x.w;
}
}a[NN];
double X(int i){return -a[i].l;}
double Y(int i){return f[i-1];}
double K(int i){return a[i].w;}
double Slope(int i,int j){return (Y(i)-Y(j)) / (X(i)-X(j));}
int main(){
scanf("%d",&n);
for(int i = 1; i <= n; ++i)
scanf("%d%d",&a[i].w,&a[i].l);
sort(a+1,a+1+n);
int maxn = 0;
for(int i = n; i >= 1; --i){
if(a[i].l <= maxn) vis[i] = 1;
maxn = max(maxn,a[i].l);
}
int cnt = 0;
for(int i = 1; i <= n; ++i)
if(!vis[i]) a[++cnt] = a[i];
n = cnt;
head = 1;tail = 0;
que[++tail] = 1;
for(int i = 1; i <= n; ++i){
while(head < tail && Slope(que[head],que[head+1]) < K(i)) ++head;
int j = que[head];
f[i] = f[j-1] + 1ll * a[j].l * a[i].w;
while(head < tail && Slope(que[tail],que[tail-1]) > Slope(que[tail],i+1)) --tail;
que[++tail] = i+1;
}
printf("%lld",f[n]);
}