https://nanti.jisuanke.com/t/42391
题意：给出两个排列矩阵，问最大相同子矩阵的元素数量。
解法：标记位置，预处理向下扩展和向右扩展。
//#include<bits/stdc++.h>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <iostream>
#include <string>
#include <stdio.h>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <string.h>
#include <vector>
#define ME(x , y) memset(x , y , sizeof(x))
#define SC scanf
#define rep(i , j , n) for(int i = j ; i <= n ; i++)
#define red(i , n , j) for(int i = n ; i >= j ; i--)
#define INF 0x3f3f3f3f
#define mod 1000000007
#define PI acos(-1)
#define pii pair<int,int>
#define fi first
#define se second
using namespace std;
typedef long long ll ;
const int maxn = 1e3+9;
const int N = 1e6+9;
int a[maxn][maxn] , b[maxn][maxn] ;//输入数组
int s[maxn] , top , val[maxn] , len[maxn];//栈
int posx[N] , posy[N];//位置标记
int dp[maxn][maxn] ;//预处理值
int vis[maxn][maxn] , ans;//标记
void work(int l){
val[l+1] = -INF , top = 0 ;
int temp = 0 ;
rep(i , 1 , l+1){
while(top && val[s[top-1]] >= val[i]){
len[s[top-1]] += temp;
temp = len[s[top-1]];
ans = max(ans , temp * val[s[top-1]]);
top--;
}
len[i] += temp;
temp = 0;
s[top++] = i;
}
}
int main()
{
int n , m ;cin >> n >> m;
rep(i , 1 , n){
rep(j , 1 , m){
scanf("%d" , &a[i][j]);
dp[i][j] = 1 ;
}
}rep(i , 1 , n){//记录每个数在b数组中的位置
rep(j , 1 , m){
scanf("%d" , &b[i][j]);
posx[b[i][j]] = i , posy[b[i][j]] = j;
}
}
rep(j , 1 , m){//向下延伸
red(i , n , 2){
int x = posx[a[i][j]];
int y = posy[a[i][j]];
if(x-1>=1 && a[i-1][j] == b[x-1][y]){
dp[i-1][j] += dp[i][j];
}
}
}
rep(i , 1 , n){
rep(j , 1 , m){
if(!vis[i][j]){//尽可能向右延伸
int l = 1 , k = 0;
val[l] = dp[i][j] , len[l] = 1;
int x = posx[a[i][j]];
int y = posy[a[i][j]];
while(y+1+k <=m && a[i][j+1+k] == b[x][y+1+k]){
val[++l] = dp[i][j+1+k] , len[l] = 1;
vis[i][j+1+k] = 1 ;
k++;
}
work(l);
}
}
}
cout << ans << endl;
return 0;
}