题解：P15884 [ICPC 2026 NAC] Jelly Fusion

· · 题解

题目大意

有一个长度为 N 的环形数组，每个元素是一个矩形果冻，第 i 个果冻的高度为 h_i，宽度为 w_i。其中第 1 个和第 N 个也相邻。

你可以进行任意次如下操作：

你可以进行任意多次融合，也可以一次都不融合。目标是让最终剩余的所有果冻的面积之和最大，其中每个果冻的面积为“高度 \times 宽度”。

给定所有果冻的初始高度和宽度，求经过若干次融合后，所有剩余果冻面积和的最大可能值。

思路

考虑首尾不相邻的情况怎么做。

那么合并相邻的等价于划分连续段。

设 dp_i 表示划分完前 i 个的答案。你首先有式子 dp_i\gets dp_{j-1}+\max(h_j,h_{j+1}\dots,h_i)\times\max(w_j,w_{j+1}\dots,w_i)。

第一想法肯定是观察其有没有决策单调性，但是好像没有。那就只能先观察一下性质。

一个自然的想法是你观察 h,w 在这一段的 \max 的位置，发现完全可以让它们一定在首尾处。

因为如果不在首尾，那就可以使这一段大小缩小，权值不变，并多出来一段，使答案更优。

所以现在可以更改其转移式为：

dp_i \gets\begin{cases} dp_{j-1}+w_jh_i\\ dp_{j-1}+h_jw_i\end{cases}

因为如果 w_i,h_j 不是最大的话并不会影响到最大答案。

然后发现该式子形如 kx+b 的形式，即 b=dp_{j-1},k=h_j,x=w_i，或 b=dp_{j-1},k=w_j,x=h_i。

于是就只需要维护若干条线段，查询在某个位置 x 上的所有线段的 y 的最大值。

这显然是李超线段树模板，可以做到 n\log V。

那么现在回到原问题，即数组是一个环的情况。

不妨利用 \max 一定在首尾的限制，找到 h_{max} 的位置，发现其肯定是某段的首尾，于是令其为第 1 个数或为第 n 个数，跑两次是一条链的情况即可。

Code

#include<bits/stdc++.h>
#define cl 1
#define cr 1000000
using namespace std;
long long n,h[300005],w[300005],answ,dp[300005];
long long a[300005],b[300005];

struct seg{
    long long cnt,d[300005*32*2],ans1;
    long double ans;
    struct a{
        long double k,b;
    }p[300005];
    long double calc(long long a,long long b) {return p[a].b+p[a].k*b*1.0;}
    long long cmp(long double x,long double y)
    {
        if (x-y>1e-10) return 1;
        if (y-x>1e-10) return -1;
        return 0;
    }
    void add(long long k,long long b)
    {
        cnt++;
        p[cnt].k=k;
        p[cnt].b=b;
    }
    void upd(long long o,long long l,long long r,long long u)
    {
        long long &v=d[o],mid=l+((r-l)>>1);
        long long bmid=cmp(calc(u,mid),calc(v,mid));
        if(bmid==1 or(!bmid and u<v)) swap(u,v);
        long long bl=cmp(calc(u,l),calc(v, l)),br=cmp(calc(u,r),calc(v,r));
        if(bl==1 or(!bl and u<v)) upd(o*2,l,mid,u);
        if(br==1 or(!br and u<v)) upd(o*2+1,mid+1,r,u);
    }
    void update(long long o,long long l,long long r,long long l1,long long r1,long long u)
    {
        if(l1<=l and r<=r1)
        {
            upd(o,l,r,u);
            return ;
        }
        long long mid=l+((r-l)>>1);
        if(l1<=mid) update(o*2,l,mid,l1,r1,u);
        if(r1>mid) update(o*2+1,mid+1,r,l1,r1,u);
    }
    void query(long long o,long long l,long long r,long long u)
    {
        if(r<u or u<l){ans=ans1=0;return ;}
        long long mid=l+((r-l)>>1);
        long double res=calc(d[o],u);
        if(l==r)
        {
            ans=res;ans1=d[o];
        }
        else
        {
            long double anss=res;
            long long anss1=d[o];
            query(o*2,l,mid,u);
            if(cmp(ans,anss)==-1);
            else if(cmp(ans,anss)==1)
            {
                anss=ans;anss1=ans1;
            }
            else
            {
                if(ans1<anss1)
                {
                    anss=ans;anss1=ans1;
                }
            }
            query(o*2+1,mid+1,r,u);
            if(cmp(ans,anss)==-1);
            else if(cmp(ans,anss)==1)
            {
                anss=ans;anss1=ans1;
            }
            else
            {
                if(ans1<anss1)
                {
                    anss=ans;anss1=ans1;
                }
            }
            ans=anss;ans1=anss1;
        }

    }
}T1,T2;
void solve()
{
    T1.cnt=T2.cnt=0;
    memset(T1.d,0,sizeof T1.d);
    memset(T2.d,0,sizeof T2.d);
    for(int i=1;i<=n;i++)
    {
        dp[i]=dp[i-1]+a[i]*b[i];
        T1.ans=T1.ans1=0;
        T1.query(1,cl,cr,a[i]);
        dp[i]=max(dp[i],(long long)T1.ans);
        T2.ans=T2.ans1=0;
        T2.query(1,cl,cr,b[i]);
        dp[i]=max(dp[i],(long long)T2.ans);

        T1.add(b[i],dp[i-1]);
        T1.update(1,cl,cr,cl,cr,T1.cnt);

        T2.add(a[i],dp[i-1]);
        T2.update(1,cl,cr,cl,cr,T2.cnt);
    }
    answ=max(answ,dp[n]);
}
int main()
{
    read(n);
    for(int i=1;i<=n;i++) read(h[i]),read(w[i]);
    long long id=0,mx=0;
    for(int i=1;i<=n;i++) if(mx<h[i]) mx=h[i],id=i;
    for(int i=1;i<=n;i++) a[i]=h[(id+i-1)%n+1];
    for(int i=1;i<=n;i++) b[i]=w[(id+i-1)%n+1];
    solve();

    for(int i=1;i<=n;i++) a[i]=h[(id+i-2)%n+1];
    for(int i=1;i<=n;i++) b[i]=w[(id+i-2)%n+1];
    solve();
    write(answ);
    return 0;
}