bzoj 1567 [JSOI2008]Blue Mary的战役地图题解

浏览数：78 / 时间：2015年06月09日

此题时限10秒，顿时惊呆，想到一个n^5解法，果断去写。

用f[i1][j1][i2][j2]表示从a矩阵的(i1,j1)和b矩阵的(i2,j2)开始哪一行有多少相同的。

然后再枚举i1,i2,j1,j2然后判断有几行。

 1 #include<iostream>
 2 #include<cstdio>
 3 using namespace std;
 4 int n;
 5 int ans=0;
 6 long long a[60][60],b[60][60];
 7 int f[60][60][60][60];
 8 int main()
 9 {
10     scanf("%d",&n);
11     for(int i=1;i<=n;i++)
12     {
13         for(int j=1;j<=n;j++)
14         scanf("%lld",&a[i][j]);
15     }
16     for(int i=1;i<=n;i++)
17     {
18         for(int j=1;j<=n;j++)
19         scanf("%lld",&b[i][j]);
20     }
21     for(int i1=1;i1<=n;i1++)
22     {
23         for(int j1=1;j1<=n;j1++)
24         {
25             for(int i2=1;i2<=n;i2++)
26             {
27                 for(int j2=1;j2<=n;j2++)
28                 {
29                     int t=0;
30                     while(t+j1<=n && t+j2<=n && a[i1][j1+t]==b[i2][j2+t])t++;
31                     if(t<0)t=0;
32                     f[i1][j1][i2][j2]=t;
33                 }
34             }
35         }
36     }
37     for(int i1=1;i1<=n;i1++)
38     {
39         for(int j1=1;j1<=n;j1++)
40         {
41             for(int i2=1;i2<=n;i2++)
42             {
43                 for(int j2=1;j2<=n;j2++)
44                 {
45                     int now=f[i1][j1][i2][j2];
46                     if(now==0)continue;
47                     int t=1;
48                     if(ans==0)ans=1;
49                     while(now && t+i1<=n && t+i2<=n)
50                     {
51                         if(f[i1+t][j1][i2+t][j2]<now)now=f[i1+t][j1][i2+t][j2];
52                         ans=max(ans,min(t+1,now));
53                         t++;
54                     }
55                 }
56             }
57         }
58     }
59     printf("%d\n",ans);
60     return 0;
61 }
62