题目：https://nanti.jisuanke.com/t/42391
题意
两个n*m的矩阵，矩阵中的数字从1~n×m随意排列，求这两个矩阵的最大公共子矩阵。
题解
将给出的第一个矩阵从上至下，从左到右重新编号为原矩阵出现的位置，如下:
5 6 7 8 1 2 3 4
1 2 3 4 ——
> 5 6 7 8
9 10 11 12 9 10 11 12
构建第二个矩阵对第一个矩阵的映射，可以得到一个新矩阵：
5 6 8 7 1 2 4 3
1 2 4 3 ——
> 5 6 8 7
12 11 10 9 12 11 10 9
最后直接对得到的这个新矩阵进行处理得到最大子矩阵。 这题引用到悬线法，可参考该题：P1169 棋盘制作 定义: l [ i ] [ j ] : 代表从 ( i , j ) (i,j) (i,j)能到达的最左位置 r [ i ] [ j ] : 代表从 ( i , j ) (i,j) (i,j)能到达的最右位置 u [ i ] [ j ] : 代表从 ( i , j ) (i,j) (i,j)向上扩展最长长度
递推公式： l [ i ] [ j ] = m a x ( l [ i ] [ j ] , l [ i − 1 ] [ j ] ) r [ i ] [ j ] = m i n ( r [ i ] [ j ] , r [ i − 1 ] [ j ] ) u [ i ] [ j ] = u [ i − 1 ] [ j ] + 1
代码
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<queue>
#include<map>
#include<set>
#include<stack>
#include<vector>
#include<algorithm>
using namespace std
;
typedef long long ll
;
#define M_PI 3.14159265358979323846
int a
[1000005],b
[1005][1005],l
[1005][1005],r
[1005][1005],u
[1005][1005];
int main()
{
ios
::sync_with_stdio(false);
int n
,m
;
cin
>>n
>>m
;
for(int i
=1;i
<=n
*m
;i
++)
{
int x
;
cin
>>x
;
a
[x
]=i
;
}
for(int i
=1;i
<=n
;i
++)
{
for(int j
=1;j
<=m
;j
++)
{
int x
;
cin
>>x
;
b
[i
][j
]=a
[x
];
l
[i
][j
]=r
[i
][j
]=j
;
u
[i
][j
]=1;
}
}
for(int i
=1;i
<=n
;i
++)
{
for(int j
=2;j
<=m
;j
++)
{
if(b
[i
][j
]==b
[i
][j
-1]+1)
l
[i
][j
]=l
[i
][j
-1];
}
for(int j
=m
-1;j
>=1;j
--)
{
if(b
[i
][j
]==b
[i
][j
+1]-1)
r
[i
][j
]=r
[i
][j
+1];
}
}
int ans
=0;
for(int i
=2;i
<=n
;i
++)
{
for(int j
=1;j
<=m
;j
++)
{
if(b
[i
][j
]==b
[i
-1][j
]+m
)
{
l
[i
][j
]=max(l
[i
][j
],l
[i
-1][j
]);
r
[i
][j
]=min(r
[i
][j
],r
[i
-1][j
]);
u
[i
][j
]=u
[i
-1][j
]+1;
}
int x
=r
[i
][j
]-l
[i
][j
]+1;
ans
=max(ans
,x
*u
[i
][j
]);
}
}
cout
<<ans
<<endl
;
return 0;
}
参考： https://blog.csdn.net/weixin_43061340/article/details/103499599
