自动搬运

查看原文

来自洛谷，原作者为

	枫林晚 **

搬运于2025-08-24 21:59:46，当前版本为作者最后更新于2018-10-01 17:50:38，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

全网唯一一篇dp题解

推广自家blog

网上貌似全部都是哈希+二分（反正我是大概baidu了翻了翻）（还有人暴力AC了的。。）

哈希还是相对于dp还是比较麻烦的。

而且正确性还有可能被卡（当然这个题不会）

而且还容易写错。

我就懒得写哈希了。

这个题，貌似和一个题目很像啊~~~

P1387 最大正方形

P1387这个题相信大家都会吧。。

不会的话看那就随便找篇题解。。

这个题就是最大正方形的加强版。

设$f[x1][y1][x2][y2]$表示，在第一个正方形中，以$(x1,y1)$为右下角，第二个正方形中以$(x2,y2)$为右下角，公共正方形最大的边长。

然后一个四重循环。

因为都是正序的，所以没有后效性。

然后转移很自然了。

和P1387一样。

$f[x1][y1][x2][y2]=min(f[x1-1][y1-1][x2-1][y2-1],min(f[x1][y1-1][x2][y2-1],f[x1-1][y1][x2-1][y2]))+1;$

上代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=52;
int f[N][N][N][N];
int a[N][N],b[N][N];
int n;
int ans;
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
			scanf("%d",&a[i][j]);
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
			scanf("%d",&b[i][j]);
	for(int x1=1;x1<=n;x1++){
		for(int y1=1;y1<=n;y1++){
			for(int x2=1;x2<=n;x2++){
				for(int y2=1;y2<=n;y2++){
					if(a[x1][y1]==b[x2][y2]){
						f[x1][y1][x2][y2]=min(f[x1-1][y1-1][x2-1][y2-1],min(f[x1][y1-1][x2][y2-1],f[x1-1][y1][x2-1][y2]))+1;
					}
					ans=max(ans,f[x1][y1][x2][y2]);
				}
			}
		}
	}
	printf("%d",ans);
	return 0;
}

虽然复杂度是$O(n^4)$不如哈希优秀。

但是好写啊！！

真是简单又自然