自动搬运

查看原文

来自洛谷，原作者为

	maojun 猫君

搬运于2025-08-24 22:05:40，当前版本为作者最后更新于2023-11-03 17:43:54，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

提供一种复杂度更优的做法。

首先可以观察到可以另 $\forall x_i\gets\left| x_i\right|,y_i\gets\left| y_i\right|$，然后求出以原点为左下角的矩形最小面积覆盖，其四倍即是答案。

考虑一对偏序 $(p,q),x_p\le x_q$ 且 $y_p\le y_q$，那么如果用矩形覆盖了 $q$ 时，就一定覆盖了 $p$。于是去掉这些不会产生贡献的点。

称以原点为左下角 $(x,y)$ 为右上角的矩形为一个点 $(x,y)$ 的原始矩形，则先设每个点都由自己的原始矩形覆盖，再合并去优化。

考虑剩下的点有什么性质。若按 $x$ 坐标递增排序，则 $y$ 坐标一定是对应递减的。那么若要合并，一定是一段连续的区间。

不然，比如 $i$ 点采用的是原始矩形，而 $i-1,i+1$ 合并，那么因为 $x_{i+1}>x_i,y_{i-1}>y_i$，所以 $i$ 点已经被包含，采用原始矩形一定不优。

于是我们可以在排序后的点上 dp，设 $f_i$ 表示前 $i$ 个点的矩形最小面积覆盖。每次枚举一个 $j\in[0,i)$ 表示合并 $(j,i]$。因为 $j+1\le i$ 所以 $x_{j+1}\le x_i,y_{j+1}\ge y_i$，所以合并出来矩形的面积为 $x_i\times y_j$。

则可得到转移方程 $f_i=\min\limits_{0\le j<i}f_j+x_i\times y_{j+1}$，复杂度 $O(n^2)$，可以通过。

#define pi pair<int,int>
#define fi first
#define se second
#define mp make_pair

typedef long long ll;
const int MAXN=5e3+5,INF=0x3f3f3f3f;
int n;pi a[MAXN];
ll dp[MAXN];

int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++){scanf("%d%d",&a[i].fi,&a[i].se);a[i].fi=abs(a[i].fi);a[i].se=abs(a[i].se);}
	sort(a+1,a+n+1,greater<pi>());// 先按 x,y 降序排序
	int mxy=0,tot=0;
	for(int i=1;i<=n;i++)		// 若 x 比该点大且 y 不比该点小，则该点被偏序
		if(a[i].se>mxy){a[++tot]=a[i];mxy=a[i].se;}
	n=tot;for(int i=1;i<=n>>1;i++)swap(a[i],a[n-i+1]);// 之前为了方便将 x 降序，这里反转一下
	memset(dp,0x3f,n+1<<3);dp[0]=0;
	for(int i=1;i<=n;i++)
		for(int j=0;j<i;j++)
			dp[i]=min(dp[i],dp[j]+a[i].fi*1ll*a[j+1].se);
	printf("%lld\n",dp[n]<<2);	// 最后乘 4
	return 0;
}

然后你发现状态其实是 $O(n)$ 级别的，凭什么复杂度到 $O(n^2)$ 了呢？

这个转移的形式特别好，典型的斜优，而且 $f$ 单调递增，一个单调队列就好了。

复杂度 $O(n\log n)$ 或 $O(n)$，瓶颈在排序。

#define pi pair<int,int>
#define fi first
#define se second
#define mp make_pair

typedef long long ll;typedef double db;
const int MAXN=5e3+5,INF=0x3f3f3f3f;
int n;pi a[MAXN];
ll dp[MAXN];

inline ll X(int i){return a[i+1].se;}inline ll Y(int i){return-dp[i];}
inline db K(int i,int j){return(Y(j)-Y(i))*1.0/(X(j)-X(i));}
int l,r,q[MAXN];
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++){scanf("%d%d",&a[i].fi,&a[i].se);a[i].fi=abs(a[i].fi);a[i].se=abs(a[i].se);}
	sort(a+1,a+n+1,greater<pi>());
	int mxy=0,tot=0;
	for(int i=1;i<=n;i++)
		if(a[i].se>mxy){a[++tot]=a[i];mxy=a[i].se;}
	n=tot;for(int i=1;i<=n>>1;i++)swap(a[i],a[n-i+1]);
	dp[q[l=r=1]=0]=0;
	for(int i=1;i<=n;i++){
		while(l<r&&K(q[l],q[l+1])<a[i].fi)l++;
		dp[i]=dp[q[l]]+a[i].fi*1ll*a[q[l]+1].se;
		while(l<r&&K(i,q[r])<K(q[r],q[r-1]))r--;
		q[++r]=i;
	}
	printf("%lld\n",dp[n]<<2);
	return 0;
}