题解：P15884 [ICPC 2026 NAC] Jelly Fusion

· · 题解

考虑枚举起点，设 f_i 表示划分了前 i 段的最大值，有转移 f_{i} \leftarrow f_j+\max(w)\times \max(h)。

这样是 O(n^3) 的，考虑优化。发现 w,h 的最大值取到端点处显然是最优的，否则你加入了一个 w,h 但是这一段贡献不变于是总贡献就减少了。

进一步的，我们不用枚举起点，w,h 的最大值肯定是端点了，于是我们令 h 的最大值分别在最前面和最后面，跑两次即可，复杂度 O(n^2)。

注意现在的转移：f_{i} \leftarrow f_j+\max(w_{j+1},w_i)\times \max(h_{j+1},h_i)，后面显然可以拆成：\max\{h_{j+1}w_{j+1},h_iw_i,w_{j+1}h_i,w_ih_{j+1}\}，发现前两个可以直接记录前缀 \max，后两个可以直接上李超线段树维护，于是时间复杂度 O(n \log n)，做完了。

:::success[code]

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e6+7;
const int MAXN=1e12+7;
struct LINE
{
    int k,b;
    LINE(){}
    LINE(int kk,int bb):k(kk),b(bb){}
}line[N];
struct Li_Seg_Tree
{
    int tr[N],ls[N],rs[N],cnt,root;
    inline void clear()
    {
        for(int i=1;i<=cnt;i++)tr[i]=ls[i]=rs[i]=0;
        root=cnt=0;
    }
    inline int calc(int id,int x){return x*line[id].k+line[id].b;}
    inline bool cmp(int A,int B,int x){return calc(A,x)>calc(B,x);}
    inline void insert(int &p,int l,int r,int id)
    {
        if(!p) p=++cnt;
        if(l==r)
        {
            tr[p]=id;
            return;
        }
        if(!tr[p])
        {
            tr[p]=id;
            return;
        }
        if(cmp(id,tr[p],l)&&cmp(id,tr[p],r))
        {
            tr[p]=id;
            return;
        }
        int mid=(l+r)>>1;
        if(cmp(id,tr[p],mid)) swap(id,tr[p]);
        if(cmp(id,tr[p],l)) insert(ls[p],l,mid,id);
        if(cmp(id,tr[p],r)) insert(rs[p],mid+1,r,id);
    }
    inline int query(int p,int l,int r,int x)
    {
        int ans=calc(tr[p],x);
        if(!p||l==r) return ans;
        int mid=(l+r)>>1;
        if(mid>=x) ans=max(ans,query(ls[p],l,mid,x));
        else ans=max(ans,query(rs[p],mid+1,r,x));
        return ans; 
    }
    inline void insert(int id)
    {
        insert(root,1,N,id);
    }
    inline int query(int x)
    {
        return query(root,1,N,x);
    }
}T1,T2;
int n;
int f[N];
int h[N],w[N];
inline int solve()
{
    T1.clear(),T2.clear();
    for(int i=0;i<=n*2+2;i++)line[i]={0,0};
    for(int i=0;i<=n;i++)f[i]=0;
    int pre1=0,pre2=0;
    line[n*2+1]={h[1],0};
    line[n*2+2]={w[1],0};
    T1.insert(n*2+1);
    T2.insert(n*2+2);
    for(int i=1;i<=n;i++)
    {
        f[i]=max({pre1+h[i]*w[i],pre2,T1.query(w[i]),T2.query(h[i])});
        pre1=max(pre1,f[i]);
        pre2=max(pre2,f[i]+h[i+1]*w[i+1]);
        line[i]={h[i+1],f[i]};
        line[i+n]={w[i+1],f[i]};
        T1.insert(i);
        T2.insert(i+n);
//      for(int j=0;j<i;j++)
//      {
//          f[i]=max(f[i],f[j]+max({h[i]*w[i],h[j+1]*w[j+1],h[j+1]*w[i],h[i]*w[j+1]}));
//      }
    }
    return f[n];
}
int H[N],W[N];
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>H[i]>>W[i];
    int Max=0,pos=0;
    for(int i=1;i<=n;i++)
    {
        if(H[i]>Max)
        {
            Max=H[i];
            pos=i;
        }
    }
    for(int i=pos,j=1;j<=n;j++,i=i%n+1)
    {
        h[j]=H[i];
        w[j]=W[i];
    }
    int ans=solve();
    for(int i=pos%n+1,j=1;j<=n;j++,i=i%n+1)
    {
        h[j]=H[i];
        w[j]=W[i];
    }
    cout<<max(ans,solve());
}

:::