【题解】P2900 [USACO08MAR] Land Acquisition G

题目链接：P2900 [USACO08MAR] Land Acquisition G

我们通过题目可以得出一个较为清晰的结论：

• 我们将所有的矩形排列起来，可以发现最后被完全包含在另一个矩形内的矩形是没有意义的。
• 这样的话我们得到的所有矩形的并是呈阶梯状的，如下图：

• 其中，中间的浅蓝色的边是没有意义的

然后我们可以推导出一个 DP 式子：

我们设 \(f_{i}\) 表示购买前 \(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]);
}