解题:JSOI 2008 Blue Mary的战略地图

 题面

 这大概不算是从零开始的DP学习系列,这不是最大子矩形吗=。=

定义$dp[x][y][xx][yy]$表示第一张地图中右下角为$(x,y)$,第二张地图中右下角为$(xx,yy)$的最大公共子矩形,然后$n^4$枚举位置,在数字相同时从左/上/左上转移即可

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 using namespace std;
 5 const int N=52;
 6 long long mapp[2][N][N],dp[N][N][N][N];
 7 long long n,ans;
 8 int main ()
 9 {
10     scanf("%lld",&n);
11     for(int i=0;i<=1;i++)
12         for(int j=1;j<=n;j++)
13             for(int k=1;k<=n;k++)
14                 scanf("%lld",&mapp[i][j][k]);
15     for(int i=1;i<=n;i++)
16         for(int j=1;j<=n;j++)
17             for(int k=1;k<=n;k++)
18                 for(int h=1;h<=n;h++)
19                     if(mapp[0][i][j]==mapp[1][k][h])
20                         ans=max(ans,dp[i][j][k][h]=min(min(dp[i-1][j][k-1][h],dp[i][j-1][k][h-1]),dp[i-1][j-1][k-1][h-1])+1);
21     printf("%lld",ans);
22     return 0;
23 }
View Code
原文地址:https://www.cnblogs.com/ydnhaha/p/9741531.html