Problem Statement
There is an $N \times M$ grid, where the square at the $i$-th row from the top and $j$-th column from the left has a non-negative integer $A_{i,j}$ written on it.
Let us choose a rectangular region $R$.
Formally, the region is chosen as follows.
- Choose integers $l_x, r_x, l_y, r_y$ such that $1 \le l_x \le r_x \le N, 1 \le l_y \le r_y \le M$.
- Then, square $(i,j)$ is in $R$ if and only if $l_x \le i \le r_x$ and $l_y \le j \le r_y$.
Find the maximum possible value of $f(R) = $ (the sum of integers written on the squares in $R$) $\times$ (the smallest integer written on a square in $R$).
Constraints
- All input values are integers.
- $1 \le N,M \le 300$
- $1 \le A_{i,j} \le 300$
这题有一万种做法。
枚举最小值 \(x\)，现在要求一个权值和最大的矩阵，满足所有数的最小值不小于 \(x\)。
设 \(s_{i,j}\) 为 \((i,j)\) 往上最多有多少个数是不小于 \(x\) 的，然后对于某一行的某个区间，他往上能有多高取决于这个区间中所有数的最小值。
区间的最小值？ 考虑单调栈求出这一行下一个和上一个比 \(v_{i,j}\) 小的区间，然后在这段区间之间的高度就取决于 \(v_{i,j}\) 的高度，二位前缀和统计即可。
#include<bits/stdc++.h>
using namespace std;
const int N=305;
typedef long long LL;
int n,m,st[N],s[N][N],ls[N],nx[N],tp,a[N][N],v[N][N];
LL p[N][N],ans;
LL ask(int ax,int ay,int bx,int by)
{
return p[bx][by]+p[ax-1][ay-1]-p[ax-1][by]-p[bx][ay-1];
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
scanf("%d",a[i]+j),p[i][j]=p[i][j-1]+a[i][j];
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
p[i][j]+=p[i-1][j];
for(int i=1;i<=300;i++)
{
for(int j=1;j<=n;j++)
{
for(int k=1;k<=m;k++)
{
if(a[j][k]>=i)
v[j][k]=v[j-1][k]+1;
else
v[j][k]=0;
}
}
for(int j=1;j<=n;j++)
{
for(int k=1;k<=m;k++)
ls[k]=0,nx[k]=m+1;
for(int k=1;k<=m;k++)
{
while(tp&&v[j][st[tp]]>v[j][k])
nx[st[tp--]]=k;
st[++tp]=k;
}
tp=0;
for(int k=m;k;k--)
{
while(tp&&v[j][st[tp]]>v[j][k])
ls[st[tp--]]=k;
st[++tp]=k;
}
for(int k=1;k<=m;k++)
ans=max(ans,1LL*i*ask(j-v[j][k]+1,ls[k]+1,j,nx[k]-1));
}
}
printf("%lld",ans);
}