LA3029最大子矩阵

https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1030

【题目描述】：给定m*n的矩阵，其中一些格子是空格F，其他是墙R。找出一个全部由空地组成的面积最大的子矩阵，输出面积。

【算法分析】：

【决策方案】：所有的子矩阵，C(n,2)*C( m,2)种，加上确认空地，大约N^6的复杂度

【限制条件】：所有的方块都是空地

【最优评判准则】：面积最大

【思路分析】：

朴素算法的复杂度是N^6,肯定不能接受，所以我们看是否记忆化扫描一些变量。一个矩阵面积的关键量是长h和宽d。参考《指南》上的思路，分别用数组表示每一个矩阵的h和d，但问题又来了，矩阵本身都有n^4种，不可能存储下来。所以我们可以换一种方式。用[I][J]代表以这一点为中心，假设这一点包含在一个空着的矩形中，那么能取到的面积是多少？为了让递递推变量更少，我们只统计up[i][j]这点向上的空格数，left[i][j].向左的最大延伸（记住，我们需要形成矩形，所以更坏的情况是向右逼近），同理，right[i][j]是右边的。

因为我们上从上到下，从两边逼近，所以：

lefts[i][j]=max(lefts[i-1][j],lo+1);

Lo是从左到有的标记量，if (map[i][j]=='F') lo=j；

Right同理，详见代码。

【难点】：思路本身（数学建模的过程）、写递推时要考虑到所有情况

【完整代码】：

 1 #include<iostream>
 2 #include<stdio.h>
 3 #include<string.h>
 4 #include<algorithm>
 5 #include<stdlib.h>
 6 #include<math.h>
 7 #include<queue>
 8 #include<vector>
 9 #include<set>
10 //#include<map>
11 #define MAXN 1000+5
12 #define MAXM 400000+5
13 #define oo 1e9
14 #define eps 0.001
15 #define PI acos(-1.0)//这个精确度高一些
16 #define REP1(i,n) for(int i=0;i<=(n);i++)
17 #define REP2(i,n) for(int i=1;i<=(n);i++)
18 #define DREP2(i,n) for(int i=(n);i>=1;i--)
19 #define LL long long
20 using namespace std;
21 
22 char map[MAXN][MAXN];
23 int up[MAXN][MAXN];
24 int rights[MAXN][MAXN];
25 int lefts[MAXN][MAXN];
26 
27 int cas,n,m;
28 
29 int main()
30 {
31     cin>>cas;
32     for(;cas;cas--)
33     {
34         cin>>n>>m;
35         REP2(i,n) REP2(j,m) {cin>>map[i][j];if (map[i][j]=='
' || map[i][j]==' ') cin>>map[i][j];}
36 //        REP2(i,n) {REP2(j,m) cout<<map[i][j]<<" ";cout<<endl;}
37         REP2(i,n)
38         {
39             REP2(j,m)
40             {
41                 if (map[i][j]=='F')
42                 {
43                     if (i==1) up[i][j]=1;else up[i][j]=up[i-1][j]+1;
44                 }else up[i][j]=0;
45             }
46             int lo=0;//清零，不确定第一列是否是墙
47             REP2(j,m)
48             {
49                 if (map[i][j]=='F')
50                 {
51                     if(i==1 || map[i-1][j]=='R') lefts[i][j]=lo+1;
52                     else lefts[i][j]=max(lefts[i-1][j],lo+1);
53                 }//取max，因为只可能向右逼近//向上取，保证宽度是逐渐减小的
54                 else
55                 {
56                     lo=j;
57                     lefts[i][j]=100001;//
58                 }
59             }
60             int ro=m+1;
61             DREP2(j,m)
62             {
63                 if (map[i][j]=='F')
64                 {
65                     if(i==1 || map[i-1][j]=='R') rights[i][j]=ro-1;
66                     else rights[i][j]=min(rights[i-1][j],ro-1);
67                 }//取max，因为只可能向右逼近//向上取，保证宽度是逐渐减小的
68                 else
69                 {
70                     ro=j;
71                     rights[i][j]=-100001;//
72                 }
73             }
74 
75         }
76         int ans=0;
77 //        REP2(i,n) {REP2(j,m) cout<<rights[i][j]<<" ";cout<<endl;}
78         REP2(i,n) REP2(j,m)
79         {
80             int S=(rights[i][j]-lefts[i][j]+1)*up[i][j]*3;
81 //            cout<<"S="<<S<<" ";
82             ans=max(S,ans);
83         }
84         cout<<ans<<endl;
85     }
86     return 0;
87 }

【关键词】：数学，递推扫描