P4147 玉蟾宫（【模板】悬线法）

题目地址

---

注意点：

• if(canGet[x][y-1])l[x][y]=max(l[x][y],l[x][y-1]);
• if(canGet[x][y-1])r[x][y]=min(r[x][y],r[x][y-1]);

---

#include<cstdio>
#include<iostream>
using namespace std;
const int MAXN=2e3,INF=2e9;
bool canGet[MAXN][MAXN];//可获取
int l[MAXN][MAXN],r[MAXN][MAXN];
int h[MAXN][MAXN];
int maxY,maxX;
int main(){
	scanf("%d%d",&maxY,&maxX);
	for(int y=1;y<=maxY;y++){
		for(int x=1;x<=maxX;x++){
			char tmp;
			cin>>tmp;
			if(tmp=='F')canGet[x][y]=1;
			else canGet[x][y]=0;
		}
	}
	for(int x=1;x<=maxX;x++){
		for(int y=1;y<=maxY;y++){
			l[x][y]=r[x][y]=x;
		}
	}
	for(int y=1;y<=maxY;y++){
		for(int x=1;x<=maxX;x++){
			if(!canGet[x][y])continue;
			if(canGet[x-1][y])l[x][y]=l[x-1][y];
			else l[x][y]=x;
		}
		for(int x=maxX;x>=1;x--){
			if(!canGet[x][y])continue;
			if(canGet[x+1][y])r[x][y]=r[x+1][y];
			else r[x][y]=x;
		}
	}
	for(int x=1;x<=maxX;x++)
		r[x][0]=INF;
	int ans=0;
	for(int y=1;y<=maxY;y++){
		for(int x=1;x<=maxX;x++){
			if(canGet[x][y]){
				h[x][y]=h[x][y-1]+1;
				if(canGet[x][y-1])l[x][y]=max(l[x][y],l[x][y-1]);
				if(canGet[x][y-1])r[x][y]=min(r[x][y],r[x][y-1]);
				ans=max(ans,(r[x][y]-l[x][y]+1)*h[x][y]);
			}
		}
	}
	cout<<ans*3<<endl;
	return 0;
}