2021“MINIEYE杯”中国大学生算法设计超级联赛(1)1008.Maximal submatrix
2021/7/21 22:22:07
本文主要是介绍2021“MINIEYE杯”中国大学生算法设计超级联赛(1)1008.Maximal submatrix,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
Maximal submatrix
题目链接
https://acm.hdu.edu.cn/showproblem.php?pid=6957
题意
给定一个 \(n\) 行 \(m\) 列的矩阵,求每个列上不递减的最大面积子矩阵
思路
令 \(sum[i][j]\) 为第 \(i\) 行第 \(j\) 列从上往下以 \(a[i][j]\) 结尾的最长不递减序列长度,枚举每一个 \(sum[i][j]\) 作为列的最长长度, 显然行长度只能延伸到左右第一个小于 \(sum[i][j]\) 的位置之前,用单调栈维护即可。
AC_Code
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int maxn = 2e3 + 50; int mp[maxn][maxn]; int sum[maxn][maxn]; int st[maxn], Lmin[maxn], Rmin[maxn], b[maxn]; void getLmin(int a[], int n){//左边第一个小于a[i]的数 int cnt = 0; st[0] = 0; for(int i = 1;i <= n;i++){ while(cnt && a[i] <= a[st[cnt]]) cnt--; Lmin[i] = st[cnt]; st[++cnt] = i; } } void getRmin(int a[], int n){//右边第一个小于a[i]的数 int cnt = 0; st[0] = n + 1; for(int i = n;i >= 1;i--){ while(cnt && a[i] <= a[st[cnt]]) cnt--; Rmin[i] = st[cnt]; st[++cnt] = i; } } int main() { std::ios::sync_with_stdio(false); int t; cin >> t; while(t--){ int n, m; cin >> n >> m; for(int i = 0;i <= n + 1;i++) for(int j = 0;j <= m + 1;j ++){ mp[i][j] = sum[i][j] = 0; } for(int i = 1;i <= n;i++){ for(int j = 1;j <= m;j++){ cin >> mp[i][j]; } } for(int i = 1;i <= n;i++){ for(int j = 1;j <= m;j++){ if(mp[i][j] >= mp[i - 1][j]) sum[i][j] = sum[i - 1][j] + 1; else sum[i][j] = 1; } } int ans = 0; for(int i = 1;i <= n;i++){ for(int j = 1;j <= m;j++){ b[j] = sum[i][j]; } getLmin(b, m); getRmin(b, m); for(int j = 1;j <= m;j++){ ans = max(ans, sum[i][j] * ( (Rmin[j] - 1) - (Lmin[j] + 1) + 1)); } } cout << ans << endl; } return 0; }
这篇关于2021“MINIEYE杯”中国大学生算法设计超级联赛(1)1008.Maximal submatrix的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-15鸿蒙生态设备数量超8亿台
- 2024-05-13TiDB + ES:转转业财系统亿级数据存储优化实践
- 2024-05-09“2024鸿蒙零基础快速实战-仿抖音App开发(ArkTS版)”实战课程已上线
- 2024-05-09聊聊如何通过arthas-tunnel-server来远程管理所有需要arthas监控的应用
- 2024-05-09log4j2这么配就对了
- 2024-05-09nginx修改Content-Type
- 2024-05-09Redis多数据源,看这篇就够了
- 2024-05-09Google Chrome驱动程序 124.0.6367.62(正式版本)去哪下载?
- 2024-05-09有没有大佬知道这种数据应该怎么抓取呀?
- 2024-05-09这种运行结果里的10.100000001,怎么能最快改成10.1?