全網唯一一篇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=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)$不如哈希優秀。

但是好寫啊！！

真是簡單又自然

轉載于:https://www.cnblogs.com/Miracevin/p/9735181.html

總結

以上是生活随笔為你收集整理的[JSOI2008]Blue Mary的战役地图——全网唯一一篇dp题解的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。