O（n^2）
1 #include<cstdio>
2 #include<algorithm>
3 using namespace std;
4 int f[105][105];
5 //f[i][j]代表以i，j为右下角的前i，j区域内的最大正方形
6 int main()
7 {
8 int n,m,ans = 0;
9 scanf("%d%d",&n,&m);
10 for(int i = 1;i <= n;i ++)
11 {
12 for(int j = 1,x;j <= m;j ++)
13 {
14 scanf("%1d",&x);
15 if(x)f[i][j] = min(min(f[i - 1][j],f[i][j - 1]),f[i - 1][j - 1]) + 1;
16 ans = max(ans,f[i][j]);
17 // printf("f[%d][%d]=%d\n",i,j,f[i][j]);
18 }
19 }
20 printf("%d\n",ans);
21 return 0;
22 }
先隔着把数取饭，在按最大正方形1操作
O（n^2）
1 #include<cstdio>
2 #include<cstring>
3 #include<algorithm>
4 using namespace std;
5 int f[1505][1505][2];
6 int a[1505][1505];
7 //f[i][j]代表以i，j为右下角的前i，j区域内的最大正方形
8 int main()
9 {
10 int n,m,ans = 0;
11 scanf("%d%d",&n,&m);
12 for(int i = 1;i <= n;i ++)
13 {
14 for(int j = 1,x;j <= m;j ++)
15 {
16 scanf("%1d",&a[i][j]);
17 }
18 }
19 for(int i = 1;i <= n;i ++)
20 {
21 for(int j = 1;j <= m;j ++)
22 {
23 if((i%2&&j%2)||(i%2==0)&&(j%2==0))a[i][j] ^= 1;
24 else continue;
25 }
26 }
27 // for(int i =1 ;i <= n;i ++)
28 // {
29 // for(int j = 1;j <= m;j ++)printf("%d",a[i][j]);
30 // printf("\n");
31 // }
32 memset(f,0,sizeof(f));
33 for(int i = 1;i <= n;i ++)
34 {
35 for(int j = 1;j <= m;j ++)
36 {
37 if(a[i][j])
38 {
39 f[i][j][1] = min(min(f[i - 1][j][1],f[i][j - 1][1]),f[i - 1][j - 1][1]) + 1;
40 }
41 else
42 {
43 f[i][j][0] = min(min(f[i - 1][j][0],f[i][j - 1][0]),f[i - 1][j - 1][0]) + 1;
44 }
45 // printf("f[%d][%d][0]=%d 1:%d\n",i,j,f[i][j][0],f[i][j][1]);
46 ans = max(ans,max(f[i][j][0],f[i][j][1]));
47 }
48 }
49 printf("%d\n",ans);
50 return 0;
51 }
题意：
求n*m矩形中，内部都为F的最大的矩形
题解：
看着仿佛和最大正方形一样，其实做法与上面不同，但是这个方法可以适用于上面以及大部分的求最大子矩形的题——悬线法
在学习悬线法的时候参考了一下题解：[leven][DP专题]悬线法 浅谈用极大化思想解决最大子矩形问题
l[i][j]表示从i，j点向上延伸的最大矩形的最左边
r[i][j]表示从i，j点向上延伸的最大矩形的最右边
up[i][j]表示从i，j点向上延伸的最大矩形的长度，看作从i，j点向上延伸的悬线的长度
(r[i][j] - l[i][j] + 1)*up[i][j]即为最大矩形的面积
正确性：因为极大矩形的边界一定是贴着限制点的或贴着边界的，而最大矩形就是极大矩形的最大值，所以在确定悬线的长度时，是遇到限制点才停止的，否则会有更大的矩形能包含这个矩形，那这个矩形就不是极大矩形了，最大矩形也一定不是这个矩形
时间复杂度：O（nm）
1 #include<cstdio>
2 #include<algorithm>
3 #include<iostream>
4 using namespace std;
5 int a[1005][1005],l[1005][1005],r[1005][1005],up[1005][1005];
6 int main()
7 {
8 int n,m;
9 scanf("%d%d",&n,&m);
10 for(int i = 1;i <= n;i ++)
11 {
12 for(int j = 1;j <= m;j ++)
13 {
14 char c;
15 cin>>c;
16 if(c == 'R')a[i][j] = 0;
17 else
18 {
19 a[i][j] = 1;
20 l[i][j] = r[i][j] = j;
21 up[i][j] = 1;//悬线的长度
22 }
23 }
24 }
25 // for(int i = 1;i <= n;i ++)
26 // {
27 // for(int j = 1;j <= m;j ++)printf("%d",a[i][j]);
28 // printf("\n");
29 // }
30
31 int ans = 0;
32 for(int i = 1;i <= n;i ++)
33 {
34 for(int j = 1;j <= m;j ++)
35 {
36 if(a[i][j] == 1 && a[i][j - 1] == 1)l[i][j] = l[i][j - 1];
37 }
38 for(int j = m;j >= 1;j --)
39 {
40 if(a[i][j] == 1 && a[i][j + 1] == 1)r[i][j] = r[i][j + 1];
41 }
42 }
43 for(int i = 1;i <= n;i ++)
44 {
45 for(int j = 1;j <= m;j ++)
46 {
47 if(i > 1)
48 {
49 if(a[i][j] == 1 && a[i - 1][j] == 1)
50 {
51 l[i][j] = max(l[i][j],l[i - 1][j]);
52 r[i][j] = min(r[i][j],r[i - 1][j]);
53 up[i][j] = up[i - 1][j] + 1;
54 }
55 }
56 // printf("l[%d][%d]=%d r[][]=%d up[][]=%d \n",i,j,l[i][j],r[i][j],up[i][j]);
57 int res = (r[i][j] - l[i][j] + 1) * up[i][j];
58 ans = max(ans,res);
59 }
60 }
61 printf("%d\n",ans * 3);
62 return 0;
63 }