悬线法

浅谈用极大化思想解决最大子矩阵问题

#include<bits/stdc++.h>
using namespace std;
int n,m,l[1010][1010],r[1010][1010],height[1010][1010];
char ch;
bool f[1010][1010];
int main()
{
    //freopen("xf.in","r",stdin);
    //freopen("xf.out","w",stdout);
    memset(f,false,sizeof(f));
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
        {
            ch=getchar();
            while(ch!='F'&&ch!='R')ch=getchar();
            if(ch=='F')f[i][j]=true;
        }
    int left,right;
    for(int i=1;i<=m;i++)r[0][i]=99999999;
    for(int i=1;i<=n;i++)
    {
        left=0;right=m+1;
        for(int j=1;j<=m;j++)
        {
            if(!f[i][j]){left=j;l[i][j]=0;continue;}
            l[i][j]=max(left,l[i-1][j]);
            if(!f[i-1][j]){height[i][j]=1;}
            else height[i][j]=height[i-1][j]+1;
        }
        for(int j=m;j>=1;j--)
        {
            if(!f[i][j]){right=j;r[i][j]=m+1;continue;}
            r[i][j]=min(right,r[i-1][j]);
        }
    }
    int ans=0;
    for(int i=1;i<=n;i++)
    for(int j=1;j<=m;j++)
    if(f[i][j])
    ans=max(ans,height[i][j]*(r[i][j]-l[i][j]-1));
    printf("%d\n",ans*3);
    return 0;
}