原题链接

题解

太巧妙了

把每个点上方的连续f长度记录下来，然后求每行的柱状图构成的矩形的最大面积

code

#include<bits/stdc++.h>
using namespace std;
int f[1005][1005]={0};
int n,m;

struct node
{
    int h,cnt;
};

int solve(int row)//每一行列上的高度，如果全部使用，不是作为左端点就是作为右端点
{
    int ans=0;
    stack<node> q;//相当于求左边最远小于自己的值，右边最远小于自己的值，单调栈解法
    for(int j=1;j<=m;j++)
    {
        int cnt=0;
        while(q.size()&&q.top().h>=f[row][j])
        {
            cnt+=q.top().cnt;//cnt代表这个点收纳了多少点
            ans=max(ans,q.top().h*cnt);//作为左端点更新，即后边遇到了比自己更小的值，然后弹出
            q.pop();//如果弹出，代表遇到了作为左端点的最远距离的点
        }

        ans=max(ans,f[row][j]*(cnt+1));//作为右端点更新，找到左边比自己小的点
        q.push({f[row][j],cnt+1});//cnt代表该元素左边有多少不小于自己的(包括自己)
    }

    int cnt=0;
    while(q.size())//有些元素没有作为左端点更新过
    {
        ans=max(ans,(cnt+1)*q.top().h);
        cnt+=q.top().cnt;
        q.pop();
    }
    return ans;
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            char op;
            cin>>op;
            if(op=='F') f[i][j]=f[i-1][j]+1;//记录以该点为下端点，最长连续f的长度
        }
    }

    int ans=0;
    for(int i=1;i<=n;i++)
    {
        ans=max(ans,solve(i));//变成求每行的最大矩形
    }

    cout<<3*ans;
    return 0;
}