P4959 题解

· · 题解

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

首先可以观察到可以另 \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;
}