luogu1387 最大正方形
- O(n^2)
- #include<cstdio>
- #include<algorithm>
- using namespace std;
- int f[105][105];
- //f[i][j] 代表以 i,j 为右下角的前 i,j 区域内的最大正方形
- int main()
- {
- int n,m,ans = 0;
- scanf("%d%d",&n,&m);
- for(int i = 1;i <= n;i ++)
- {
- for(int j = 1,x;j <= m;j ++)
- {
- scanf("%1d",&x);
- if(x)f[i][j] = min(min(f[i - 1][j],f[i][j - 1]),f[i - 1][j - 1]) + 1;
- ans = max(ans,f[i][j]);
- // printf("f[%d][%d]=%d\n",i,j,f[i][j]);
- }
- }
- printf("%d\n",ans);
- return 0;
- }
luogu1681 最大正方形 2
先隔着把数取饭, 在按最大正方形 1 操作
- O(n^2)
- #include<cstdio>
- #include<cstring>
- #include<algorithm>
- using namespace std;
- int f[1505][1505][2];
- int a[1505][1505];
- //f[i][j] 代表以 i,j 为右下角的前 i,j 区域内的最大正方形
- int main()
- {
- int n,m,ans = 0;
- scanf("%d%d",&n,&m);
- for(int i = 1;i <= n;i ++)
- {
- for(int j = 1,x;j <= m;j ++)
- {
- scanf("%1d",&a[i][j]);
- }
- }
- for(int i = 1;i <= n;i ++)
- {
- for(int j = 1;j <= m;j ++)
- {
- if((i%2&&j%2)||(i%2==0)&&(j%2==0))a[i][j] ^= 1;
- else continue;
- }
- }
- // for(int i =1 ;i <= n;i ++)
- // {
- // for(int j = 1;j <= m;j ++)printf("%d",a[i][j]);
- // printf("\n");
- // }
- memset(f,0,sizeof(f));
- for(int i = 1;i <= n;i ++)
- {
- for(int j = 1;j <= m;j ++)
- {
- if(a[i][j])
- {
- f[i][j][1] = min(min(f[i - 1][j][1],f[i][j - 1][1]),f[i - 1][j - 1][1]) + 1;
- }
- else
- {
- f[i][j][0] = min(min(f[i - 1][j][0],f[i][j - 1][0]),f[i - 1][j - 1][0]) + 1;
- }
- // printf("f[%d][%d][0]=%d 1:%d\n",i,j,f[i][j][0],f[i][j][1]);
- ans = max(ans,max(f[i][j][0],f[i][j][1]));
- }
- }
- printf("%d\n",ans);
- return 0;
- }
luogu4147 玉蟾宫
题意:
求 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)
- #include<cstdio>
- #include<algorithm>
- #include<iostream>
- using namespace std;
- int a[1005][1005],l[1005][1005],r[1005][1005],up[1005][1005];
- int main()
- {
- int n,m;
- scanf("%d%d",&n,&m);
- for(int i = 1;i <= n;i ++)
- {
- for(int j = 1;j <= m;j ++)
- {
- char c;
- cin>>c;
- if(c == 'R')a[i][j] = 0;
- else
- {
- a[i][j] = 1;
- l[i][j] = r[i][j] = j;
- up[i][j] = 1;// 悬线的长度
- }
- }
- }
- // for(int i = 1;i <= n;i ++)
- // {
- // for(int j = 1;j <= m;j ++)printf("%d",a[i][j]);
- // printf("\n");
- // }
- int ans = 0;
- for(int i = 1;i <= n;i ++)
- {
- for(int j = 1;j <= m;j ++)
- {
- if(a[i][j] == 1 && a[i][j - 1] == 1)l[i][j] = l[i][j - 1];
- }
- for(int j = m;j>= 1;j --)
- {
- if(a[i][j] == 1 && a[i][j + 1] == 1)r[i][j] = r[i][j + 1];
- }
- }
- for(int i = 1;i <= n;i ++)
- {
- for(int j = 1;j <= m;j ++)
- {
- if(i> 1)
- {
- if(a[i][j] == 1 && a[i - 1][j] == 1)
- {
- l[i][j] = max(l[i][j],l[i - 1][j]);
- r[i][j] = min(r[i][j],r[i - 1][j]);
- up[i][j] = up[i - 1][j] + 1;
- }
- }
- // printf("l[%d][%d]=%d r[][]=%d up[][]=%d \n",i,j,l[i][j],r[i][j],up[i][j]);
- int res = (r[i][j] - l[i][j] + 1) * up[i][j];
- ans = max(ans,res);
- }
- }
- printf("%d\n",ans * 3);
- return 0;
- }
来源: http://www.bubuko.com/infodetail-3283301.html