【bzoj3039】玉蟾宫悬线法

悬线法是一种更优秀的枚举方式，保证了枚举悬线的集合包含了极大子矩形所在的集合，而且由最大子矩形一定是极大子矩形的定理可知，这种枚举方式可以求出最大子矩形。

具体做法是维护矩形中每个元素对应最近的左边和右边的障碍点，再维护一个高度数组记录下每个点向上可以延伸多高，还有对应的矩形向左向右可以到达的最大宽度。

代码如下

#include <bits/stdc++.h>

using namespace std;

const int maxn=1e3+10;

int n,m,a[maxn][maxn];char s[2];

int lpos[maxn][maxn],rpos[maxn][maxn],l[maxn][maxn],r[maxn][maxn],h[maxn][maxn];

void read_and_parse(){

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

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

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

			scanf("%s",s);

			if(s[0]=='F')a[i][j]=1;

		}

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

		int pos=0;//初始障碍点是0

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

			if(a[i][j])lpos[i][j]=pos;

			else pos=j,l[i][j]=0;//如果是障碍点，l，r 数组也要跟着初始化，避免对下面不是障碍点的递推造成影响

		}

		pos=m+1;

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

			if(a[i][j])rpos[i][j]=pos;

			else pos=j,r[i][j]=m+1;

		}

	}

}

void solve(){

	int ans=0;

	for(int j=1;j<=m;j++)r[0][j]=m+1;

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

		for(int j=1;j<=m;j++)if(a[i][j]){

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

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

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

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

		}

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

}

int main(){

	read_and_parse();

	solve();

	return 0;

}

巴特西

【bzoj3039】玉蟾宫悬线法

最新文章

热门文章

巴特西

【bzoj3039】玉蟾宫 悬线法

最新文章

热门文章

【bzoj3039】玉蟾宫悬线法