发布时间：2024-07-31

最大子矩阵模型

定义数组
$h_{i,j}$ 表示第j列以i为底所能到达的最大高度,即碰到障碍物或者上边界，全部初始化为1

$l_{i,j}$ 表示在第i行中j所能到达的最左边界，初始化为j

$r_{i,j}$同理

然后从左枚举更新l,从右枚举更新r,具体视题目而定

当 $a_{i,j} 和a_{i-1,j}$满足题目要求能存在于同一矩形时：

• $ h_{i,j}=h_{i-1,j}+1 $
• $ l_{i,j}=max(l_{i,j},l_{i-1,j}) $
• $ r_{i,j}=min(r_{i,j},r_{i-1,j}) $

void solve(){
    int n,m;
    cin>>n>>m;
    vector<vector<char>> a(n+1,vector<char>(m+1));
    vector<vector<int>> h(n+1,vector<int>(m+1)),l(n+1,vector<int>(m+1)),r(n+1,vector<int>(m+1));
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin>>a[i][j];
            h[i][j]=1;
            l[i][j]=r[i][j]=j;
        }
        for(int j=2;j<=m;j++){
            if(a[i][j]==a[i][j-1]&&a[i][j]=='F')l[i][j]=l[i][j-1];
        }
        for(int j=m-1;j>=1;j--){
            if(a[i][j]==a[i][j+1]&&a[i][j]=='F')r[i][j]=r[i][j+1];
        }
    }
    ll ans=0;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(i>1){
                if(a[i][j]==a[i-1][j]&&a[i][j]=='F'){
                    h[i][j]=h[i-1][j]+1;
                    l[i][j]=max(l[i][j],l[i-1][j]);
                    r[i][j]=min(r[i][j],r[i-1][j]);
                }
            }
            if(a[i][j]=='F')ans=max(ans,(ll)(r[i][j]-l[i][j]+1)*h[i][j]);
        }
    }
    cout<<ans*3;
}