LA3029最大子矩阵

发布时间：2026-01-11 11:34

矩阵式决策: 利用矩阵图评估项目风险与收益 #生活技巧# #团队建设技巧# #团队决策方法#

生活随笔收集整理的这篇文章主要介绍了 LA3029最大子矩阵小编觉得挺不错的,现在分享给大家,帮大家做个参考.

题意：
给你一个n*m的矩阵<每个格子不是'F'就是'R'>，让你找一个最大的'F'矩阵，输出他的面积*3。

思路：
比较经典的题目了，现在想起来比较好想，以前的话想着很费劲，最早先用瓶颈法在杭电上过了一个数据范围比较小的，今天的这个目测瓶颈法过不去，瓶颈法的时间复杂度是O(n^3)的，今天的这个我们可以用另外一个也是比较经典的一个方法，时间复杂度是O(n^2),思路是我们可以枚举每个矩形向上延伸的最大距离，然后把这个最大距离（竖线）像左的最大平移距离和向右的最大平移距离求出来，高H[i][j]，左最大距离L[i][j] ,右最大平移距离R[i][j]，然后当前答案是 now = (L[i][j] + R[i][j] - 1) * H[i][j].这个很容易理解，每一个最大的子举行一定是某一个点的最长向上距离*左右活动范围得来的。然后对于更新的时候是这样的：

如果当前是'R'那么H[i][j] = 0 ,否则H[i][j] = H[i-1][j] + 1
如果当前是'R'那么L[i][j] = 0 ,否则如果当前的上一个是'R'或者当前是第一行，那么L[i][j] = ls ,否则L[i][j] = min(ls ,L[i-1][j]);ls 是当前行前面的最大延续长度，更新R[i][j]的时候类似，具体细节看代码。

#include<stdio.h>
#include<string.h>

#define N 1000 + 5

int map[N][N];
int H[N][N] ,L[N][N] ,R[N][N];

int minn(int x ,int y)
{
return x < y ? x : y;
}

int maxx(int x ,int y)
{
return x > y ? x : y;
}

int main()
{
int t ,n ,m ,i ,j;
int ls ,rs;
char str[5];
scanf("%d" ,&t);
while(t--)
{
scanf("%d %d" ,&n ,&m);
for(i = 1 ;i <= n ;i ++)
for(j = 1 ;j <= m ;j ++)
{
scanf("%s" ,str);
map[i][j] = (str[0] == 'F');
}
int Ans = 0;
memset(H ,0 ,sizeof(H));
memset(L ,0 ,sizeof(L));
memset(R ,0 ,sizeof(R));
for(i = 1 ;i <= n ;i ++)
{
for(j = 1 ;j <= m ;j ++)
if(map[i][j]) H[i][j] = H[i-1][j] + 1;
else H[i][j] = 0;
ls = 0;
for(j = 1 ;j <= m ;j ++)
{
map[i][j] ? ls ++ : ls = 0;
map[i][j] ? ((i == 1 || !map[i-1][j]) ? L[i][j] = ls : L[i][j] = minn(ls ,L[i-1][j])) : L[i][j] = 0;
}
rs = 0;
for(j = m ;j >= 1 ;j --)
{
map[i][j] ? rs ++ : rs = 0;
map[i][j] ? ((i == 1 || !map[i-1][j]) ? R[i][j] = rs : R[i][j] = minn(rs ,R[i-1][j])) : R[i][j] = 0;
if(map[i][j])
{
int now = (L[i][j] + R[i][j] - 1) * H[i][j];
if(Ans < now) Ans = now;
}
}
}
printf("%d\n" ,Ans * 3);
}
return 0;
}

总结

以上是生活随笔为你收集整理的LA3029最大子矩阵的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。

网址：LA3029最大子矩阵 https://www.yuejiaxmz.com/news/view/1434680

⬅️上一篇：做家务纳入义务教育！每个孩子都要

➡️下一篇：东莞整理师收纳师培训

LA3029最大子矩阵

总结

相关内容

随便看看

最新动态分享

热点动态分享

专题

推荐动态分享