总体思路：悬线DP

洛谷链接

题意的化简： 题目中要我们求最大的01相间的矩阵（四边形）和正方形。 对于处理矩阵，只需：(Map[i][j]!=Map[i][j-1])/*证明相邻两个颜色不同，符合题意 */

对于正方形和长方形，在代码中会继续讲解；

题目的核心：

悬线DP

我们需要枚举第i行第j列往上（<i）的最大合法合法矩阵（01相间）， 于是我们设三个二维数组： Left[i][j]:表示第i行第j列可以到达的最左边的位置； Right[i][j]:表示第i行第j列可以到达的最右边的位置； Up[i][j]:表示第i行第j列可以到达最上方的长度； 在输入数据时，顺便对着三个数组进行初始化，Left和Right的初始化为j，因为这时我们还不知道左右延伸的长度，所以都为原点；Up则为1，因为我们也不知道每个矩阵最上面能到达哪个位置。

我们对Left和Right分别进行二维的初始化，求出上述中我们想得到的量，代码：

for(register int i=1;i<=N;i++) for(register int j=2;j<=M;j++)//注意这里的循环：从最左边往右边扫 if(Map[i][j]!=Map[i][j-1])//如果相邻两个符合条件，连接 Left[i][j]=Left[i][j-1]; for(register int i=1;i<=N;i++) for(register int j=M-1;j>0;j--)//注意这里的循环：从最右边往左边扫 if(Map[i][j]!=Map[i][j+1])//如果相邻两个符合条件，连接 Right[i][j]=Right[i][j+1];

Up、Left和Right的递推公式： Up[i][j]=Up[i-1][j]+1; Left[i][j]=max(Left[i][j],Left[i−1][j]; Right[i][j]=min(Right[i][j],Right[i-1][j]; （前提是他们都是合法相邻）

Q：为什么Left要用max，而Right要用min？ A：因为你想，这个枚举出来的图形的左右肯定是参差不齐的，要想使它变成四边形，肯定要找到左边和右边线段的最小值，右边的最小值用min（靠近中轴），左边的最小值要用max（靠近中轴）： 如图，红色代表每一行相对于中轴（蓝线）的合法矩阵，紫色，橙色分别代表左，右的最短线段，肯定从紫色，橙色截取，得到了绿色的最大矩阵。

Q：为什么Up数组要从上一行加一? A：因为Up数组是用来统计从第i行第j列可以到达最上方的长度，所记录的不是一个坐标（像Right和Left）,而是一个最远距离的值。 Q：为什么Up数组不像Left和Right数组一样统计向上延伸的最短值？ A；因为Up数组记录的是中轴的长度，而中轴只有一条，所以无需做此操作。

而对于Up数组，我们可以边DP边初始化。

代码：

#include <bits/stdc++.h> using namespace std; int Left[2020][2020],Right[2020][2020]; int Up[9999][2020],DP[2020][2020]; int Map[2020][2020],N,M; int ACanswer1,ACanswer2; int main(void){ scanf("%d%d",&N,&M); for(register int i=1;i<=N;i++){ for(register int j=1;j<=M;j++){ scanf("%d",&Map[i][j]); Right[i][j]=j; Left[i][j]=j; Up[i][j]=1; } }//输入数据并进行初始化 for(register int i=1;i<=N;i++) for(register int j=2;j<=M;j++) if(Map[i][j]!=Map[i][j-1]) Left[i][j]=Left[i][j-1]; for(register int i=1;i<=N;i++) for(register int j=M-1;j>0;j--) if(Map[i][j]!=Map[i][j+1]) Right[i][j]=Right[i][j+1]; //对每个点的左右进行延伸 ACanswer1=ACanswer2=1;//长方形和正方形的初始值都为1 for(register int i=1;i<=N;i++){ for(register int j=1;j<=M;j++){ if((i>1)&&(Map[i][j]!=Map[i-1][j])){//如果此位置上方还有位置，并且与上方合法（上方为0我为1，上方为1我为0） Left[i][j]=max(Left[i][j],Left[i-1][j]); Right[i][j]=min(Right[i][j],Right[i-1][j]);//对左右两边进行截取（取最小值） Up[i][j]=Up[i-1][j]+1;//初始化（中轴++） } int Num1=Right[i][j]-Left[i][j]+1;//细节，左右间隔是还要减一的 int Num2=min(Num1,Up[i][j]);//找到长和宽谁短（用于计算正方形面积） ACanswer1=max(ACanswer1,Num2*Num2);//正方形面积打类 ACanswer2=max(ACanswer2,Num1*Up[i][j]);//长方形面积打类 } } cout<<ACanswer1<<endl; cout<<ACanswer2<<endl; return 0;//输出并结束 }

结语：

祝大家在NOIP2019中RP++！！！