【题意】给定01矩阵，求最大全1子矩阵。n,m<=1000。

【算法】动态规划（悬线法）

【题解】★对于01矩阵中的任意一个全1极大子矩阵，都可以在其上边界遇到的障碍点处悬线到下边界的点x，则点x唯一对应了一个极大子矩阵，那么至多有n*m个极大子矩阵，而最大子矩阵一定是极大子矩阵，故求解复杂度O(nm)。

预处理L[i][j]表示(i,j)向左延伸的最左位置，R[i][j]同理。

设h[i][j]表示(i,j)向上的悬线高度，l[i][j]表示(i,j)代表的极大子矩阵向左延伸的最左位置，r[i][j]同理。

a[i][j]=1，则有：h[i][j]=h[i-1][j]　　l[i][j]=max{ l[i-1][j] , L[i][j]}　　r[i][j]=min{ r[i-1][j] , R[i][j] }

注意初始化r[0][i]=m+1。

#include
      
       #include
       
        using namespace std;const int maxn=1010;int n,m,a[maxn][maxn],L[maxn][maxn],R[maxn][maxn],l[maxn][maxn],r[maxn][maxn],h[maxn][maxn],ans=0;char s[10];int main(){    scanf("%d%d",&n,&m);    for(int i=1;i<=n;i++){        for(int j=1;j<=m;j++){            scanf("%s",s);            if(s[0]=='F')a[i][j]=1;else a[i][j]=0;        }    }    for(int i=1;i<=n;i++){        int left=0,right=m+1;        for(int j=1;j<=m;j++)if(a[i][j])L[i][j]=left;else left=j;        for(int j=m;j>=1;j--)if(a[i][j])R[i][j]=right;else right=j;    }    for(int i=1;i<=m;i++)r[0][i]=m+1;    for(int i=1;i<=n;i++){        for(int j=1;j<=m;j++){            if(a[i][j]){                h[i][j]=h[i-1][j]+1;                l[i][j]=max(l[i-1][j],L[i][j]);                r[i][j]=min(r[i-1][j],R[i][j]);            }            else h[i][j]=0,l[i][j]=0,r[i][j]=m+1;            ans=max(ans,h[i][j]*(r[i][j]-l[i][j]-1));        }    }    printf("%d",ans*3);    return 0;}
       
      

 

图大点稀的情况可以用另一种方法寻找极大子矩阵：从左到右枚举障碍点，考虑向右扩展障碍点并压缩矩阵大小（左边界必须包含原障碍点），复杂度O(S^2)，这是基于极大子矩阵一定四个边界都被障碍点卡住的思想。注意在左右边界遍布障碍点。