2019牛客暑期多校训练营（第二场）H Second Large Rectangle

示例一：

输入  ：

1 2

01

输出：

0

示例二：

输入  ：

1 3

101

输出：

1

示例三（自己自测找错误用的）：

输入  ：

6 6
100111
111011
111111
111111
111111
101111

输出：

16

题意：在由1和0构成的矩形中找到由仅由1构成的第二大的矩形。（前缀和思维）

解题思路：（1）这是比赛后看别人代码的解法，比赛中自己也有这思路，但没考虑周到。运用前缀和思想算出每个位置前面到这个位置一共有多少个连续的1，然后从左上角开始往下算，每次记录当前位置的长度和位置（位置后面用来计算矩形的高度），每次算出当前最大矩形的大小和次大矩形的大小，更新答案。

（2）dfs，感觉自己剪枝做得不够好所以一直超时，还没想出如何不超时的剪枝方法，先留着，复杂度为o（n³），通过率为95%。

不说了，贴代码：

（1）ac代码

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 const int maxn=1e3+20;
 4 int a[maxn][maxn],max_1=0,max_2=0;///a数组记录每个位置的前缀和，max_1和max_2为最大和次大
 5 char ss[maxn][maxn];
 6 struct node
 7 {
 8     int num,ins;
 9 }pp[maxn];///记录当前位置的长度和位置
10 void update(int summ)///更新最大值和次大值
11 {
12     if(summ>max_1){
13         swap(max_1,max_2);swap(summ,max_1);
14     }
15     else if(summ>max_2)swap(summ,max_2);
16 }
17 int main()
18 {
19     int n,m;
20     scanf("%d%d",&n,&m);
21     for(int i=1; i<=n; i++)
22         scanf("%s",ss[i]);
23     for(int i=1;i<=n;i++){
24         for(int j=0;j<m;j++){
25             if(ss[i][j]=='0')a[i][j+1]==0;
26             else if(ss[i][j]=='1')a[i][j+1]=a[i][j]+1;
27         }
28     }
29     for(int j=1; j<=m; j++)
30     {
31         int r=0;
32         for(int i=1; i<=n; i++)
33         {
34             int book=i;
35             while(r&&pp[r].num>a[i][j]){
36                 update((i-pp[r].ins)*pp[r].num);
37                 update((i-pp[r].ins-1)*pp[r].num);
38                 book=min(book,pp[r].ins);
39                 r--;
40             }
41             pp[++r]={a[i][j],book};
42         }
43         while(r){
44                 update(((n+1)-pp[r].ins)*pp[r].num);
45                 update(((n+1)-pp[r].ins-1)*pp[r].num);
46                 r--;
47             }
48     }
49     printf("%d\n",max_2);
50     return 0;
51 }

 

（2）有剪枝通过的大佬教我一下

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 const int maxn=1e3+20;
 4 int a[maxn][maxn],max_1=0,max_2=0,t;///a数组记录每个位置的前缀和，max_1和max_2为最大和次大
 5 int jlen=0,ilen=0,rec;///用于记录最小长度，最高高度和当前面积
 6 char ss[maxn][maxn];
 7 void dfs(int x,int y)
 8 {
 9     if(a[x][y])
10     {
11         if(a[x][y]>=jlen)
12         {
13             ilen++;
14             rec=ilen*jlen;
15             if(rec>max_1){
16                 swap(max_1,max_2);swap(rec,max_1);}
17             else if(rec>max_2)
18                 swap(rec,max_2);
19             dfs(x-1,y);
20         }
21         else if(a[x][y]<jlen)
22         {
23             ilen++,jlen=a[x][y];
24             rec=ilen*jlen;
25             if(rec>max_1)
26                 t=max_1,max_1=rec,max_2=t;
27             else if(rec>max_2)
28                 max_2=rec;
29             dfs(x-1,y);
30         }
31     }
32     return;
33 }
34 int main()
35 {
36     int n,m,x,book=0;
37     scanf("%d%d",&n,&m);
38     for(int i=1; i<=n; i++){
39         scanf("%s",ss[i]);
40         for(int j=0; j<m; j++)
41         {
42             if(j==0&&ss[i][0]=='1')
43                 a[i][1]=1,book++;
44             else if(ss[i][j]=='0')
45                 a[i][j+1]=0;
46             else if(ss[i][j]=='1')
47                 a[i][j+1]=a[i][j]+1,book++;
48         }
49     }
50     for(int i=1; i<=n; i++)
51     {
52         for(int j=1; j<=m; j++)
53         {
54             if(a[i][j])
55             {
56                 ilen=1,jlen=a[i][j];
57                 rec=ilen*jlen;
58                 if(rec>max_1)
59                     t=max_1,max_1=rec,max_2=t;
60                 else if(rec>max_2)
61                     max_2=rec;
62                 dfs(i-1,j);
63             }
64         }
65     }
66     printf("%d\n",max_2);
67     return 0;
68 }