解题思路

悬线法、DP

对于每个位置,

记录

以这个位置为下界的最大矩阵的

左边界 :$l[i][j]$

右边界:$r[i][j]$

高,也就是上下界差:$h[i][j]$

当然啦,暴力做是会$T$的(废话),于是可以充分利用已经求出的信息

进行$\to\ DP$

递推式:

在每个位置更新答案,当然,在C的位置不能选,直接continue

Code:

#include<bits/stdc++.h>
#define ll long long
#define N 4007
using namespace std;
int n,m,l[N][N],r[N][N],h[N][N];
char b[N][N];
ll k,ans,L;
inline int read() {
    int s=0;
    char c=getchar();
    while(!isdigit(c)) c=getchar();
    while(isdigit(c)) s=(s<<1)+(s<<3)+c-'0',c=getchar();
    return s;
}
int main()
{
    int i,j;
    char c;
    while((n=read())) {
        m=read(),k=read(),ans=0;
        for(i=1;i<=n;i++) {//读入
            c=getchar();
            while(c=='\n'||c=='\r') c=getchar();
            b[i][1]=c,l[i][1]=r[i][1]=1;
            for(j=2;j<=m;j++)//初始化
                b[i][j]=getchar(),l[i][j]=r[i][j]=j;
        }
        for(i=1;i<=n;i++) {//处理出每个位置左右的障碍点
            for(j=2;j<=m;j++)
                if(b[i][j]==b[i][j-1])
                    l[i][j]=l[i][j-1];
            for(j=m-1;j;j--)
                if(b[i][j]==b[i][j+1])
                    r[i][j]=r[i][j+1];
        }
        for(i=1;i<=n;i++) {
            for(j=1;j<=m;j++) {
                if(b[i][j]=='C') continue;
                if(b[i][j]==b[i-1][j]) {//更新可能的矩形
                    l[i][j]=max(l[i][j],l[i-1][j]);
                    r[i][j]=min(r[i][j],r[i-1][j]);
                    h[i][j]=h[i-1][j]+1;
                }
                else h[i][j]=1;
                L=r[i][j]-l[i][j]+1;
                ans=max(ans,L*h[i][j]);//用矩形面积公式更新
            }
        }
        printf("%lld\n",ans*k);//别忘了要乘上单位面积
    }
    return 0;
}

devil.