P1169 [ZJOI2007] 棋盘制作

left[i][j]:代表从(i,j)(i,j)能到达的最左位置

right[i][j]:代表从(i,j)(i,j)能到达的最右位置

up[i][j]:代表从(i,j)(i,j)向上扩展最长长度.

悬线法：

假设求没有黑色格子的最大矩形，那么我们可以考虑对每个点计算，首先算出这个点向左延申的左端点和向右的右端点，然后计算向上的高度直到遇到黑色方块（此时要更新最大左端点和最小右端点，因为要保证向上延申的都是白块），然后就可以计算最大矩形面积。

那么这道题可以将两个相邻点是否一样，如果不一样看成白块。

代码：

#include <bits/stdc++.h>
#define int long long
#define fi first 
#define se second
#define all(v) v.begin(),v.end()
using namespace std;
const int inf = 0x3f3f3f3f3f3f3f;
const int N = 2005;
int n,m;
int a[N][N];
int ll[N][N],rr[N][N],up[N][N];

void solve(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin>>a[i][j];
            up[i][j] = 1;
            ll[i][j] = rr[i][j] = j;
        }
    }
    //计算左边能到达的最远
    for(int i=1;i<=n;i++){
        for(int j=2;j<=m;j++){
            if(a[i][j]!=a[i][j-1]){
                ll[i][j] = ll[i][j-1];
            }
        }
    }
    //计算右边能到达的最远
    for(int i=1;i<=n;i++){
        for(int j=m-1;j>=1;j--){
            if(a[i][j]!=a[i][j+1]){
                rr[i][j] = rr[i][j+1];
            }
        }
    }

    int ans1 = 0;
    int ans2 = 0;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(i>1 && a[i][j]!=a[i-1][j]){
                ll[i][j] = max(ll[i-1][j],ll[i][j]);
                rr[i][j] = min(rr[i-1][j],rr[i][j]);
                up[i][j] = up[i-1][j] + 1;
            }
            int len = rr[i][j] - ll[i][j] + 1;
            int hei = up[i][j];
            int min1 = min(len,hei);
            ans1 = max(ans1,min1*min1);
            ans2 = max(ans2,len * hei);
        }
    }

    cout<<ans1<<"\n"<<ans2<<"\n";

    
}

signed main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int T = 1;
    //cin>>T;
    while(T--){
        solve();
    }
    return 0;
}