题意

一个01矩阵，要找最大的全是1的矩阵

题解

垂线法的裸题，复习一下

CODE:

#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
using namespace std;
const int N=1005;
int n,m;
int a[N][N];
int L[N][N],R[N][N];//这个点可以往左走的最大    往右走的最大 
int f[3][N][N];//往上   往左   往右 
void DP ()
{for (int u=1;u<=n;u++){L[u][0]=0;for (int i=1;i<=m;i++){if (a[u][i]==0) continue;L[u][i]=L[u][i-1]+1;f[1][u][i]=L[u][i];if (a[u-1][i]==1){f[0][u][i]=f[0][u-1][i]+1;f[1][u][i]=min(f[1][u][i],f[1][u-1][i]);}}}for (int u=1;u<=n;u++){R[u][m+1]=0;for (int i=m;i>=1;i--){if (a[u][i]==0) continue;R[u][i]=R[u][i+1]+1;f[2][u][i]=R[u][i];if (a[u-1][i]==1){f[2][u][i]=min(f[2][u][i],f[2][u-1][i]);}}}
}
int main()
{memset(a,0,sizeof(a));scanf("%d%d",&n,&m);for (int u=1;u<=n;u++)for (int i=1;i<=m;i++){char ch=getchar();while (ch!='R'&&ch!='F') ch=getchar();a[u][i]=(ch=='F');}/*printf("\n");for (int u=1;u<=n;u++){for (int i=1;i<=m;i++)printf("%d ",a[u][i]);printf("\n");}printf("\n");*/DP();
/* for (int u=1;u<=n;u++){for (int i=1;i<=m;i++)printf("%d ",f[1][u][i]);printf("\n");}*/int ans=0;for (int u=1;u<=n;u++)for (int i=1;i<=m;i++){ans=max(ans,(f[0][u][i]+1)*(f[1][u][i]+f[2][u][i]-1));//if ((f[0][u][i]+1)*(f[1][u][i]+f[2][u][i]-1)==20)//  printf("%d %d %d %d %d\n",u,i,f[0][u][i],f[1][u][i],f[2][u][i]);}printf("%d\n",ans*3);       return 0;
}