Tony Zhao

题目大意

给你一个'F'和'R'组成的矩阵，求这个矩阵的最大的只由'F'组成的子矩阵的大小。

这题可以用单调栈理解，但是同时还有一种高大上的理解方法：悬线法。

假定对于每一个点(i,j)伸出一条竖直向上的直线，这个线就是悬线。特殊定义对于一个不合法的点它的悬线长为0,如果这个点上方的点不合法也是0. 所以对于每一条悬线，我们都可以轻松推出一个东西：向上最远推出的边界（只考虑本列）。

对于每一个可能的子矩阵一定有一个限制条件——可能是某一列的列宽很矮，限制了整个子矩阵的高。但是我们在延伸的时候不需要考虑这个问题——因为对于每一个限制条件都会考虑到，不会出现一个矩阵应该走限制但是没走从而漏掉关键的子矩阵。

设$L_{i,j}$表示点(i,j)向左的最远延伸距离，$R_{i,j}$表示点(i,j)向右的最远延伸距离。首先只考虑本行的情况，很轻松推出$L_{i,j},R_{i,j}$. 而对于多行之间干扰的情况，如果(i,j)的上一行是有效的（悬线长度不为0）此时的长度就是上一行和本行应有长度的较小值.

最终答案就是$\max((L_{i,j}+R_{i,j}-1)(H_{i,j}+1))$

这里有一个东西需要特别注意：

对于一个点的L和R值，有两个值：一个是临时的“只考虑本行情况下的值”，另一个是“最终的考虑所有的值”。的确是用第一种和第二种取最大值，但是需要注意的是用第一种更新第一种，也只用第一种更新第一种。所以需要进行两次遍历，第一次求出第一种值，第二次求出第二种值。如果一次求出两个值的话就会发现有的值考虑不到延伸情况。

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define N 1010
int n,m,h[N][N],l[N][N],r[N][N],ans;
char in[2];
bool mp[N][N];
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;++i) for(int j=1;j<=m;++j)
    {
        scanf("%s",in);
        mp[i][j]=(in[0]=='F');
    }
    for(int i=1;i<=n;++i) for(int j=1;j<=m;++j) if(mp[i][j])
    {
        if(mp[i-1][j]) h[i][j]=h[i-1][j]+1;
        l[i][j]=l[i][j-1]+1;
    }
    for(int i=1;i<=n;++i) for(int j=1;j<=m;++j) if(mp[i][j]&&mp[i-1][j]) l[i][j]=min(l[i-1][j],l[i][j]);
    for(int i=1;i<=n;++i) for(int j=m;j;j--) if(mp[i][j]) r[i][j]=r[i][j+1]+1;
    for(int i=1;i<=n;++i) for(int j=m;j;j--) if(mp[i][j]&&mp[i-1][j]) r[i][j]=min(r[i-1][j],r[i][j]);
    /*
    for(int i=1;i<=n;++i) {for(int j=1;j<=m;++j)printf("%d ",h[i][j]);printf("\n");}
    for(int i=1;i<=n;++i) {for(int j=1;j<=m;++j)printf("%d ",l[i][j]);printf("\n");}
    for(int i=1;i<=n;++i) {for(int j=1;j<=m;++j)printf("%d ",r[i][j]);printf("\n");}
    */
    for(int i=1;i<=n;++i) for(int j=1;j<=m;++j) ans=max(ans,((h[i][j]+1)*(r[i][j]+l[i][j]-1)));
    printf("%d\n",ans*3);
    return 0;
}

BZOJ 3039 玉蟾宫

题目大意