BZOJ 3039: 玉蟾宫

BZOJ 3039: 玉蟾宫"/>

BZOJ 3039: 玉蟾宫

首先求每一个点向上最多延伸的长度
然后就是左右延伸这个怎么线性搞出来
正解似乎是单调站的样子
其实可以换个姿势，写一个类似于并查集的东西，直接看代码吧，代码非常简单
ps：想要卡进本题排名第一页一定要用getchar

#include<set>
#include<map>
#include<ctime>
#include<queue>
#include<cmath>
#include<cstdio>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define T 1111
using namespace std;
int h[T],l[T],r[T];
int n,m,ans;
int main()
{scanf("%d%d",&n,&m);for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){char c=getchar();while(c!='R'&&c!='F')c=getchar();if(c=='F')h[j]++; else h[j]=0;l[j]=r[j]=j;}for(int j=1;j<=m;j++)if(h[j])while(h[j]<=h[l[j]-1])l[j]=l[l[j]-1];for(int j=m;j>=1;j--)if(h[j]){while(h[j]<=h[r[j]+1])r[j]=r[r[j]+1];ans=max(ans,h[j]*(r[j]-l[j]+1));}}cout<<ans*3;return 0;
}