P4147 玉蟾宫(悬线法求最大子矩阵)

悬线法 ，\(l_{i,j},r_{i,j},up_{i,j}\) 分别表示 \((i,j)\) 这个点向左，右，上能到达的远点。然后面积就很好办了。具体实现见代码。

然而，还有更优秀的算法，可是我还没学会嘤嘤嘤，可以看看这题：P1578 奶牛浴场

#include<bits/stdc++.h>

using namespace std;

const int N=1005;

int a[N][N],l[N][N],r[N][N],n,m,mp[N][N],ans;

int rd()

{

	#define gc() getchar()

	char c=gc();

	while(c!='R'&&c!='F')c=gc();

	return c=='F'?1:0;

}

int max(const int &a,const int &b){return a>b?a:b;}

int min(const int &a,const int &b){return a<b?a:b;}

int main()

{

	scanf("%d%d",&n,&m);

	for(int i=1;i<=n;++i)

		for(int j=1;j<=m;++j)

			mp[i][j]=rd(),l[i][j]=r[i][j]=j,a[i][j]=1;

	for(int i=1;i<=n;++i)

		for(int j=2;j<=m;++j)

			if(mp[i][j]&&mp[i][j-1])

				l[i][j]=l[i][j-1];

	for(int i=1;i<=n;++i)

		for(int j=m-1;j>=1;--j)

			if(mp[i][j]&&mp[i][j+1])

				r[i][j]=r[i][j+1];

	for(int i=1;i<=n;++i)

	{

		for(int j=1;j<=m;++j)

		{

			if(i>1&&mp[i][j]&&mp[i-1][j])

			{

				a[i][j]=a[i-1][j]+1;

				l[i][j]=max(l[i][j],l[i-1][j]);

				r[i][j]=min(r[i][j],r[i-1][j]);

			}

			ans=max(ans,(r[i][j]-l[i][j]+1)*a[i][j]);

		}

	}

	printf("%d\n",ans*3);

	return 0;

}

巴特西

P4147 玉蟾宫(悬线法求最大子矩阵)

最新文章

热门文章