一.矩形的最大面积——单调栈
(1)例题
P4147 玉蟾宫 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
(2)讲解(摘自题解)
问题转化:
-
n行m列土地,求最大矩形面积,我们把问题拆分成n个子问题来解决.
-
对于每一行,依次记录每行向上一直是F土地的可延伸的最大距离,记为f(i,j).
- 当前元素(i,j)为F,则f(i,j)=f(i-1,j)+1.
- 当前元素(i,j)为R,则f(i,j)=0.
-
我们记录这个数组有什么用呢?这就可以转化为单调栈维护的问题了.
具体思路:
-
对于每一个子问题,我们维护一个单调递增的单调栈.我们定义一个结构体(其中记录的两个元素分别是当前行第j个矩形的f值,以及它在当前已加入栈中矩形高度的排名).
-
我们考虑当前加入第k个矩形的情况.
-
当前矩形高度大于栈顶,直接加入即可,因为没有比它大的元素,那么他的排名为1.
-
当前矩形高度小于栈顶,则不断取出栈顶,直到栈为空或者栈顶矩形的高度比当前矩形小.在出栈过程中,我们累计被弹出的矩形的宽度之和,并且每弹出一个矩形,就用它的高度乘上累计的排名(是累计,因为在它入栈后还有比它大的元素入栈)来更新答案.
-
这样为什么是对的呢?这是因为:如果当前要加入矩形的f值(即当前矩形的高度比上一个小),那么该矩形想利用前面的矩形一起构成一个大矩形是,这块矩形的高度不可能超过该矩形自己的高度,则记录前面元素的高度就没有用处了.而宽度还有用处(因为当前矩形高度较小,与比它高的矩形的宽度总和相乘,在此矩形出栈时,要用它来更新答案).所以我们要记一个当前已加矩形的高度排名(无论是在栈里还是已经出栈).而又因为每个元素只被弹栈一次,所以不会有重复情况.
-
在所有矩形(m个)都考虑过后,我们再用还没有弹栈的元素再来个新一波答案,直到栈空
-
(3)AC
#include<bits/stdc++.h>
#define maxn 1005
using namespace std;
int n,m;
int ans,maxs;
struct node{
int hign,length;
}sta[maxn];
int f[maxn][maxn]; //记录每行每列的高
void work(int x){
int top=1,len=0;
maxs=0;
sta[top].hign=f[x][1];
sta[top].length=1;
for(int i=2;i<=m;i++){
len=0;
//维持递增
while(sta[top].hign>=f[x][i] && top>0){
len+=sta[top].length; //继承长度,毕竟高的可以,低的也必可以
maxs=max(maxs,sta[top--].hign*len);
}
sta[++top].hign=f[x][i];
sta[top].length=len+1;
}
len=0;
//同上while
while(top){
len+=sta[top].length;
maxs=max(maxs,sta[top--].hign*len);
}
ans=max(ans,maxs);
}
int main(){
scanf("%d%d",&n,&m);
char c;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin>>c;
if(c=='F') f[i][j]=f[i-1][j]+1;
}
}
//枚举每一行,解决子问题
for(int i=1;i<=n;i++) work(i);
printf("%d",ans*3);
return 0;
}
二.正方形的最大面积——dp
(1)例题
P1387 最大正方形 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
(2)讲解
就是一个简单的dp,dp状态转移方程式为:
dp[i][j]=min(min(dp[i-1][j],dp[i][j-1]),dp[i-1][j-1])+1;
(3)AC
#include<bits/stdc++.h>
#define maxn 101
using namespace std;
int n,m;
int a[maxn][maxn],dp[maxn][maxn];
int ans;
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
scanf("%d",&a[i][j]);
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(a[i][j]==1){
dp[i][j]=min(min(dp[i-1][j],dp[i][j-1]),dp[i-1][j-1])+1;
}
ans=max(ans,dp[i][j]);
}
}
cout<<ans;
}