抄题解的代码。。。

加上个人理解：

最终答案肯定是某个极大子矩形。那么一定会存在一个底边上的点\(a\)使得\(up[i][j]\)（最小的那个）等于矩形的高。枚举每个点，把它当做点\(a\)，那么答案一定会被枚举到。既然知道了矩形的高（该点向上能到的最高位置（最大长度）） ，那么这一段高度内（第\(j\)列）所有点向右的最小值和向左的最大值为矩形的左右边界。

（直接更改\(lef\),\(righ\)的值真吓人）

#include
    
     #include
     
      #include
      
       #define LL long long #define re register#define N 2001using namespace std;inline int read(){    int ans=0,w=1;    char c=getchar();    while((c<'0'||c>'9')&&c!='-') c=getchar();    if(c=='-') { w=-1; c=getchar(); }    while(c>='0'&&c<='9')    { ans=ans*10+c-'0'; c=getchar(); }    return ans*w;}int res[N][N],lef[N][N],righ[N][N],up[N][N];int n,m,ans1,ans2;int main(){    n=read(),m=read();    for(re int i=1;i<=n;i++)     for(re int j=1;j<=m;j++)     {        res[i][j]=read();        lef[i][j]=righ[i][j]=j;        up[i][j]=1;     }    for(re int i=1;i<=n;i++)     for(re int j=2;j<=m;j++)      if(res[i][j]!=res[i][j-1])       lef[i][j]=lef[i][j-1];    for(re int i=1;i<=n;i++)     for(re int j=m-1;j>0;j--)      if(res[i][j]!=res[i][j+1])       righ[i][j]=righ[i][j+1];    for(re int i=1;i<=n;i++)     for(re int j=1;j<=m;j++)     {        if(i>1&&res[i][j]!=res[i-1][j])        {            lef[i][j]=max(lef[i][j],lef[i-1][j]);            righ[i][j]=min(righ[i][j],righ[i-1][j]);            up[i][j]=up[i-1][j]+1;        }        int a=righ[i][j]-lef[i][j]+1;        int b=min(a,up[i][j]);        ans1=max(ans1,b*b);        ans2=max(ans2,a*up[i][j]);     }    printf("%d\n%d\n",ans1,ans2);    return 0;}
      
     
    

（抄题解的代码）

反思\(rect\)那道题：（P1387的样例都不过啊！）

只枚举左上角的话：

4 4

0 1 1 1

1 1 1 0

0 1 1 0

1 1 0 1

不考虑正方形，考虑矩形的话，答案应该是6

按考场上的做法：当枚举到（1,2）时，因为它向右最远长度为3，向下最远长度为4，所以会取行2到4的\(minh\)为1，列1到4的\(minl\)为1。很明显漏掉了答案。

\(update:\)重点！！！差点又因为这种情况错了一次。

而本题（棋盘制作）的题解就避免了这种情况。

还是附一个考场的代码吧：

#include
    
     #include
     
      #include
      
       #include
       
        using namespace std;int n,m,a[1004][1005],ans;int lie[1005][1005],ha[1005][1005];int minl[1005][1005][12],minh[1005][1005][12];bool flag;bool check(int x,int y,int u,int v){    int ch;    for(int i=x;i<=u;i++)    {        ch=a[i][y+1]-a[i][y];        for(int j=y+1;j<=v;j++)         if(a[i][j]-a[i][j-1]!=ch) return false;    }    for(int i=y;i<=v;i++)    {        ch=a[x+1][i]-a[x][i];        for(int j=x+1;j<=u;j++)         if(a[j][i]-a[j-1][i]!=ch) return false;    }    return true;}void work1(){    for(int i=1;i<=n;i++)    {        for(int j=1;j<=m;j++)        {            if(a[i][j]==a[i][j-1]&&j!=1)             ha[i][j]=ha[i][j-1]-1,minl[i][j][0]=ha[i][j];            else            {                int t;                for(t=j+1;t<=m;t++)                  if(a[i][t]!=a[i][j]) break;                ha[i][j]=t-j; minl[i][j][0]=ha[i][j];            }        }    }    for(int i=1;i<=m;i++)    {        for(int j=1;j<=n;j++)        {            if(a[j-1][i]==a[j][i]&&j!=1)             lie[j][i]=lie[j-1][i]-1,minh[j][i][0]=lie[j][i];            else            {                int t;                for(t=j+1;t<=n;t++)                  if(a[t][i]!=a[j][i]) break;                lie[j][i]=t-j; minh[j][i][0]=lie[j][i];            }        }    }//  for(int i=1;i<=n;i++)//   for(int j=1;j<=m;j++)//   {//      cout<
        
         <<"*"<
         
          <
         
        
       
      
     
    

写了这么多行才20 分，真惨！