P4147玉蟾宫——最大子矩阵

悬线法裸题。

代码如下：

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int const MAXN=1005,MAXM=1005;
int n,m,lf[MAXN][MAXM],rt[MAXN][MAXM],ans,a[MAXN][MAXM],sta[MAXM],top;
bool d[MAXN][MAXM];
int main()
{
    scanf("%d%d",&n,&m);
    char dc;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
        {
            cin>>dc;
            if(dc=='R')d[i][j]=1;
            else
            {
                for(int k=i-1;k;k--)
                    if(d[k][j])
                    {
                        a[i][j]=i-k;
                        break;
                    }
                if(!a[i][j])a[i][j]=i;
//                printf("a[%d][%d]=%d
",i,j,a[i][j]);
            }
        }
    for(int i=1;i<=n;i++)
    {
        memset(sta,0,sizeof sta);
        top=0;
        for(int j=1;j<=m;j++)
        {
            while(a[i][j]<=a[i][sta[top]]&&top)top--;
            lf[i][j]=sta[top];
            sta[++top]=j;
        }
        memset(sta,0,sizeof sta);
        top=0;sta[top]=m+1;
        for(int j=m;j;j--)
        {
            while(a[i][j]<=a[i][sta[top]]&&top)top--;
            rt[i][j]=sta[top];
            sta[++top]=j;
        }
//        for(int j=1;j<=m;j++)
//            printf("lf[%d][%d]=%d rt[%d][%d]=%d
",i,j,lf[i][j],i,j,rt[i][j]);
    }
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
        {
            int l,r;
            if(d[i][j])continue;
            if(!d[i][j]&&i>1)
            {
                l=max(lf[i][j],lf[i-1][j]);
                r=min(rt[i][j],rt[i-1][j]);
                ans=max(ans,a[i][j]*(r-l-1));
            }
            else ans=max(ans,rt[i][j]-lf[i][j]-1);
        }
    printf("%d",3*ans);
    return 0;
}