次元传送门：洛谷P1169
思路
浙江省选果然不一般
用到一个从来没有听过的算法 悬线法：
所谓悬线法 就是用一条线（长度任意）在矩阵中判断这条线能到达的最左边和最右边及这条线的长度 即可得到这个矩阵的最大值
那么我们定义3个数组
l[i][j]表示(i,j)能到达最左边的坐标
r[i][j]表示(i,j)能到达最右边的坐标
up[i][j]表示(i,j)能向上最大距离 即线的长度
那么状态转移方程得出：
l[i][j]=max(l[i][j],l[i-
1][j]);
//满足条件的最大值为左边（因为要矩形）
r[i][j]=min(r[i][j],r[i-
1][j]);
//满足条件的最小值为右边
up[i][j]=up[i-
1][j]+
1;
//向上的距离与上一层有关
最后统计正方形和矩形（长方形）的最大面积
代码
#include<iostream>
using namespace std;
#define maxn 2020
int map[maxn][maxn],l[maxn][maxn],r[maxn][maxn],up[maxn][maxn];
int n,m,ans1,ans2;
int main()
{
cin>>n>>
m;
for(
int i=
1;i<=n;i++
)
for(
int j=
1;j<=m;j++
)
{
cin>>
map[i][j];
l[i][j]=r[i][j]=j;
//初始化为自身
up[i][j]=
1;
//初始为1
}
for(
int i=
1;i<=n;i++
)
for(
int j=
2;j<=m;j++)
//推出左数组
if(map[i][j]!=map[i][j-
1]) l[i][j]=l[i][j-
1];
for(
int i=
1;i<=n;i++
)
for(
int j=m-
1;j>=
1;j--)
//推出右数组
if(map[i][j]!=map[i][j+
1]) r[i][j]=r[i][j+
1];
for(
int i=
1;i<=n;i++
)
for(
int j=
1;j<=m;j++
)
{
if(i>
1&&map[i][j]!=map[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]);
//判断上面可以到达的最左边
up[i][j]=up[i-
1][j]+
1;
//长度+1
}
int a=r[i][j]-l[i][j]+
1;
//此矩阵的横向长度
int b=min(a,up[i][j]);
//正方形边长为横向长纵向长的最小值
ans1=max(ans1,b*b);
//正方形
ans2=max(ans2,a*up[i][j]);
//矩形
}
cout<<ans1<<endl<<
ans2;
}
转载于:https://www.cnblogs.com/BrokenString/p/9911692.html
