MLE笛卡尔树55pts求助
  • 板块P4147 玉蟾宫
  • 楼主czy0407
  • 当前回复0
  • 已保存回复0
  • 发布时间2024/3/11 11:35
  • 上次更新2024/3/11 16:09:31
查看原帖
MLE笛卡尔树55pts求助
91433
czy0407楼主2024/3/11 11:35
#include<bits/stdc++.h>
using namespace std;
const int N=1e3+10;
int n,m,a[N],b[N],c[N],sta[N],son[N][2],ans,sz[N],i;
char s[N];
void dfs(int x)
{
	if(!x)return;
	int ls=son[x][0],rs=son[x][1];
	dfs(ls);dfs(rs);
	sz[x]+=sz[ls]+sz[rs];
	ans=max(ans,sz[x]*b[x]);
}	
int main()
{
	ios::sync_with_stdio(0);
	cin>>n>>m;
	for(i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			cin>>s[j];
			if(s[j]=='F')a[j]=1,b[j]=a[j]+c[j];
		}
		for(int j=1;j<=m;j++)c[j]=b[j];
		int top=0;
		for(int j=1;j<=m;j++)
		{
			sz[j]=1;
			while(top&&b[j]<b[sta[top]])son[j][0]=sta[top--];
			if(sta[top])son[sta[top]][1]=j;
			sta[++top]=j;
		}
		dfs(sta[1]);
		memset(sz,0,sizeof(sz));
		memset(sta,0,sizeof(sta));
		memset(son,0,sizeof(sta));
		memset(b,0,sizeof(sta));
	}
	cout<<ans*3;
	return 0;
} 
2024/3/11 11:35
加载中...