P10623 [ICPC2013 WF] Pirate Chest 题解

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

## 思路

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

$$
b[i][j]=\min\limits_{k=0}^{o-1}a[i+k][j]
$$

你应当预处理出数组 $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

```cpp
#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);
}
```

正在渲染内容...