最大子矩阵 递推 扫描线
2021/9/7 23:36:19
本文主要是介绍最大子矩阵 递推 扫描线,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
#include<bits/stdc++.h> #include<iostream> using namespace std; typedef long long ll; int dir[4][2]={{1,0},{-1,0},{0,1},{0,-1}}; ll mod=19260817; char cun[1005][1005]; int down[1005][1005]; int lefts[1005][1005]; int righ[1005][1005]; int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); int t; cin>>t; while(t--) { int n,m; cin>>n>>m; char temp; for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) { cin>>cun[i][j]; } } for(int i=1;i<=n;i++) { int ro=m+1,lo=0; for(int j=1;j<=m;j++) { if(cun[i][j]=='R') { down[i][j]=0; lefts[i][j]=0; righ[i][j]=0; lo=j; } else { down[i][j]=down[i-1][j]+1; if(down[i][j]!=1) lefts[i][j]=min(lefts[i-1][j],j-lo-1); else lefts[i][j]=j-lo-1; } } for(int j=m;j>=1;j--) { if(cun[i][j]=='R') { ro=j; } else { if(down[i][j]!=1) righ[i][j]=min(righ[i-1][j],ro-j-1); else righ[i][j]=ro-j-1; } } } int ans=0; for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) { ans=max(ans,(righ[i][j]+lefts[i][j]+1)*down[i][j]); } } cout<<ans*3<<'\n'; for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) { down[i][j]=0; lefts[i][j]=0; righ[i][j]=0; } } } }
Uvalive 3029 left right代表移动的极限距离 down代表能往上走的极限距离
#include<bits/stdc++.h>#include<iostream>
using namespace std;typedef long long ll;int dir[4][2]={{1,0},{-1,0},{0,1},{0,-1}};ll mod=19260817;char cun[1005][1005];int down[1005][1005];int lefts[1005][1005];int righ[1005][1005];int main(){
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); int t; cin>>t; while(t--) { int n,m; cin>>n>>m; char temp;
for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) { cin>>cun[i][j];
} }
for(int i=1;i<=n;i++) { int ro=m+1,lo=0; for(int j=1;j<=m;j++) { if(cun[i][j]=='R') { down[i][j]=0; lefts[i][j]=0; righ[i][j]=0; lo=j; } else { down[i][j]=down[i-1][j]+1; if(down[i][j]!=1) lefts[i][j]=min(lefts[i-1][j],j-lo-1); else lefts[i][j]=j-lo-1; } } for(int j=m;j>=1;j--) { if(cun[i][j]=='R') {
ro=j; } else { if(down[i][j]!=1) righ[i][j]=min(righ[i-1][j],ro-j-1); else righ[i][j]=ro-j-1; } } } int ans=0; for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) { ans=max(ans,(righ[i][j]+lefts[i][j]+1)*down[i][j]); } } cout<<ans*3<<'\n'; for(int i=1;i<=n;i++) { for(int j=1;j<=m;j++) { down[i][j]=0; lefts[i][j]=0; righ[i][j]=0; } } }
}
这篇关于最大子矩阵 递推 扫描线的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 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?