Problem

传送门

Solution

为最大子矩阵的模板题。
使用悬线法。

论文还是看了不久的 orz 下面两篇是我找到稍微好看一点的。
论文名为王知昆编撰的《浅谈用极大化思想解决最大子矩形问题》。
Clove_unique - 转载
konjak 魔芋 - 转载（带了点稍微详细些的图）

也可以选择下载附件。这个文档也是从百度文库上弄下来的
浅谈用极大化思想解决最大子矩形问题.doc

说是最大子矩形问题，其实也可以应用到矩阵当中。如论文所说的，使用悬线法会更加恰当，并且非常简洁易懂。
注意有个小坑，就是你需要特判一下这玩意是不是障碍点。障碍点不应该进行枚举。如果上一个是障碍点，也不应该更新 L 或 R。
L 或 R 我认为应该事先预处理一下。

下方是代码 ww

// Code by ajcxsu
// Problem: Codevs P2491
#include<bits/stdc++.h>
using namespace std;

const int N=1010;
bool mz[N][N];
int H[N][N],L[N][N],R[N][N];

int main() {
    ios::sync_with_stdio(false);
    int n,m;
    cin>>n>>m;
    char ch;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++) {
            cin>>ch;
            mz[i][j]=(ch=='R');
        }
    for(int i=1;i<=n;i++){
        L[i][1]=1;
        for(int j=2;j<=m;j++)
            if(mz[i][j-1]) L[i][j]=j;
            else L[i][j]=L[i][j-1];
    }
    for(int i=1;i<=n;i++){
        R[i][m]=m;
        for(int j=m-1;j>=1;j--)
            if(mz[i][j+1]) R[i][j]=j;
            else R[i][j]=R[i][j+1];
    }
    int S=0;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++) {
            if(i!=1) {
                if(mz[i-1][j]) H[i][j]=1;
                else {
                    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]);
                }
            }
            else H[i][j]=1;
            if(!mz[i][j]) S=max(S,(R[i][j]-L[i][j]+1)*H[i][j]);
        }
    cout<<S*3<<endl;
    return 0;
}

本文链接：https://pst.iorinn.moe/archives/sol_codevs_2491.html
许可： https://pst.iorinn.moe/license.html
若无特别说明，博客内的文章默认将采用 CC BY 4.0 许可协议 进行许可☆