空间换时间例题学习笔记2
2026-05-31 14:47:33
发布于：上海
2阅读
0回复
0点赞
题意：有一个得矩阵。每个格子里写着""或者""。找出其中的一个子矩阵，其元素均为""并且面积最大。输出它得面积乘以3得数值。
这里我们采用”悬线法“。
将矩阵中字母为”“的格子称为障碍格。将字母为”“的格子成为”非障碍格“。
对于一个非障碍格，可以延伸出一跳一直往上延伸、碰到障碍格子或上边界则停止的线，这条线往往被成为悬线。
最大面积矩阵的高一定是一条悬线。处理每一个非障碍格子时，找出它的悬线长度，并且计算这条悬线往左或往右分别最远可以到达的位置，最后计算面积，比较最大值。
需要以下的预处理工作。
1.数组：悬线高度。初始值为1。如果同列上一行格子非障碍格子，则为上方格子值加一。
2.数组：这个格子往左可以找到的最远的非障碍格的列坐标。首先将其设置为本身的列坐标，然乎对于每一行，从左往右循环，如果同一行左边的格子非障碍，则值是左边格子的值。
3.数组：跟差不多吧。我不打了。
接下来，对每一个非障碍格子计算它的选线可以往左和往右的最远地方。当这个非障碍格的上方也是非障碍格，如果上方格子的值更大，则更新为上方格子的的值。也一样。最后算面积就好了。
代码：
#include<bits/stdc++.h>
using namespace std;
const int N=1e3+5;
char a[N][N];
int h[N][N],l[N][N],r[N][N];
int ans;
int main(){
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin>>a[i][j];
h[i][j]=1,l[i][j]=r[i][j]=j;
}
for(int j=2;j<=m;j++){
if(a[i][j-1]=='F')l[i][j]=l[i][j-1];
}
for(int j=m-1;j>=1;j--){
if(a[i][j+1]=='F')r[i][j]=r[i][j+1];
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(a[i][j]=='F'){
if(a[i-1][j]=='F'){
h[i][j]=h[i-1][j]+1;
if(l[i-1][j]>l[i][j])l[i][j]=l[i-1][j];
if(i>1&&r[i-1][j]<r[i][j])r[i][j]=r[i-1][j];
}
ans=max(ans,h[i][j]*(r[i][j]-l[i][j]+1));
}
}
}
cout<<ans*3;
return 0;
}
这里空空如也
有帮助，赞一个