悬线法求极大子矩阵

h为高度，l为左端极值，r为右端极值

就有递推方程

当块为R时

h[i][j]=0

l[i][j]=0

r[i][j]=m+1

当块为F时

h[i][j]=h[i-1][j]

l[i][j]=min(l[i-1][j],不为R的最左端+1)

r[i][j]=max(r[i-1][j],不为R的最右端-1)

然后搞一搞就可以了

1 #include
      
        2 #include
       
         3 using namespace std; 4 int i,j,k,a,b,c,n,m,sm; 5 char s; 6 bool e[1001][1001]={}; 7 int r[1001][1001]={}; 8 int h[1001][1001]={}; 9 int l[1001][1001]={};10 int ri[1001][1001]={};11 int li[1001][1001]={};12 int main()13 {14     cin>>n>>m;15     for(i=1;i<=n;i++)16     {17           for(j=1;j<=m;j++)18           {19                  cin>>s;20                  if(s=='R')21                  {22                            e[i][j]=1;23                  }24                  else25                  {26                      e[i][j]=0;27                  }28           }29     }30     for(i=1;i<=n;i++)31     {32           k=0;           33           for(j=1;j<=m;j++)34           {35                  if(e[i][j]==0)36                  {37                       li[i][j]=k;38                  }39                  else40                  {41                      k=j;42                      l[i][j]=0;43                      r[i][j]=m+1;44                  }45           }46           k=m+1;47           for(j=m;j>=1;j--)48           {49                  if(e[i][j]==0)50                  {51                       ri[i][j]=k;52                  }53                  else54                  {55                      k=j;56                  }57           }                   58     }59     for(j=1;j<=m;j++)60     {61           l[0][j]=0;62           r[0][j]=m+1;63     } 64     sm=0;          65     for(j=1;j<=m;j++)66     {67           for(i=1;i<=n;i++)68           {69                  if(e[i][j]==0)70                  {71                      h[i][j]=h[i-1][j]+1;72                      l[i][j]=max(l[i-1][j],li[i][j]+1);73                      r[i][j]=min(r[i-1][j],ri[i][j]-1);74                      sm=max(sm,(r[i][j]-l[i][j]+1)*h[i][j]);75                  }76           }77     }78     cout<