[JSOI2008]Blue Mary的战役地图——全网唯一一篇dp题解

时间:2021-06-10 14:55:24

全网唯一一篇dp题解

网上貌似全部都是哈希+二分(反正我是大概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=;
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=;i<=n;i++)
for(int j=;j<=n;j++)
scanf("%d",&a[i][j]);
for(int i=;i<=n;i++)
for(int j=;j<=n;j++)
scanf("%d",&b[i][j]);
for(int x1=;x1<=n;x1++){
for(int y1=;y1<=n;y1++){
for(int x2=;x2<=n;x2++){
for(int y2=;y2<=n;y2++){
if(a[x1][y1]==b[x2][y2]){
f[x1][y1][x2][y2]=min(f[x1-][y1-][x2-][y2-],min(f[x1][y1-][x2][y2-],f[x1-][y1][x2-][y2]))+;
}
ans=max(ans,f[x1][y1][x2][y2]);
}
}
}
}
printf("%d",ans);
return ;
}

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

但是好写啊!!

真是简单又自然