P10623 [ICPC2013 WF] Pirate Chest 题解

_•́へ•́╬_ · 2024-06-21 09:56:46 · 题解

如果你会二维单调队列（不知道为啥要叫这个名字，见 P2216），它的思想对本题很有帮助。

思路

最外层枚举箱子的行数 o，处理出 b 数组：

你应当预处理出数组 maxn，maxn[j] 表示 o\times j 的矩形中的最小值最大是多少，即不考虑水面上涨时 o\times j 的箱子最深是多少。

你已经有 b 数组了，所以 \forall i\in[0,n-o]，把 b[i][] 建笛卡尔树跑一下就可以了，具体见我的代码。

然后把水面上涨考虑进去就可以了。

复杂度 \mathcal O(n^3)，但是暴力最值分治（依然不知道为啥要叫这个名字，本质就是暴力用 st 表建笛卡尔树）\mathcal O(n^3\log n) 也能过。

code

#include<stdio.h>
#include<vector>
#define N 509
using namespace std;
inline char nc()
{
    static char buf[99999],*l,*r;
    return l==r&&(r=(l=buf)+fread(buf,1,99999,stdin),l==r)?EOF:*l++;
}
inline void read(int&x)
{
    char c=nc();for(;c<'0'||'9'<c;c=nc());
    for(x=0;'0'<=c&&c<='9';x=(x<<3)+(x<<1)+(c^48),c=nc());
}
int n,m,p,q,a[N][N],b[N][N],maxn[N],lc[N],rc[N];long long ans;vector<int>s;
inline void work(int i,int j,int l,int r)
{
    if(j>>31)return;
    maxn[r-l+1]=max(maxn[r-l+1],b[i][j]);
    work(i,lc[j],l,j-1);work(i,rc[j],j+1,r);
}
main()
{
    read(p);read(q);read(n);read(m);
    for(int i=0;i<n;++i)for(int j=0;j<m;b[i][j]=1<<30,read(a[i][j++]));
    for(int o=1;(o<=p||o<=q)&&o<=n;++o)
    {
        for(int i=0;i<=n-o;++i)for(int j=0;j<m;++j)
            b[i][j]=min(b[i][j],a[i+o-1][j]);
        for(int i=0;i<=m;maxn[i++]=0);
        for(int i=0;i<=n-o;++i)
        {
            s.clear();
            for(int j=0;j<m;++j)
            {
                lc[j]=rc[j]=-1;
                for(;s.size()&&b[i][s.back()]>=b[i][j];
                    lc[j]=s.back(),s.pop_back());
                if(s.size())rc[s.back()]=j;
                s.emplace_back(j);
            }
            work(i,s[0],0,m-1);
        }
        for(int j=m-1;j;--j)maxn[j]=max(maxn[j+1],maxn[j]);
        for(int j=1;((o<=p&&j<=q)||(o<=q&&j<=p))&&j<=m;++j)
        {
            long long d=maxn[j]+((long long)(o)*j*maxn[j]-1)/(n*m-o*j);
            ans=max(ans,o*j*d);
        }
    }
    printf("%lld",ans);
}