题解 P4398 【[JSOI2008]Blue Mary的战役地图】
枫林晚
2018-10-01 17:50:38
# 全网唯一一篇dp题解
推广自家[blog](https://www.cnblogs.com/Miracevin/p/9735181.html)
网上貌似全部都是哈希+二分（反正我是大概baidu了翻了翻）（还有人暴力AC了的。。）
哈希还是相对于dp还是比较麻烦的。
而且正确性还有可能被卡（当然这个题不会）
而且还容易写错。
我就懒得写哈希了。
这个题，貌似和一个题目很像啊~~~
[P1387 最大正方形](https://www.luogu.org/problemnew/show/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;$
上代码：
```cpp
#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)$不如哈希优秀。
但是好写啊！！
~~真是简单又自然~~