LA 3029 City Game
2024-09-01 16:53:56
LA 3029
求最大子矩阵问题,主要考虑枚举方法,直接枚举肯定是不行的,因为一个大矩阵的子矩阵个数是指数级的,因此应该考虑先进行枚举前的扫描工作。
使用left,right,up数组分别记录从i,j位置可以向左,右,上扩展的最大距离,那么最终只需要枚举每一个方块即可使用(right-left)*up
#include <iostream>
#include <cstring>
#define M(a) memset(a,0,sizeof(a))
using namespace std;
const int maxn=1e3+;
char mat[maxn][maxn];
int up[maxn][maxn],lef[maxn][maxn],righ[maxn][maxn];
int m,n; void Init()
{
cin>>m>>n;
for(int i=;i<=m;i++)
{
for(int j=;j<=n;j++)
cin>>mat[i][j];
}
M(up);
M(lef);
M(righ);
} void Work()
{
for(int i=;i<=m;i++)
{
int l=;
for(int j=;j<=n;j++)
{
up[i][j]=up[i-][j]+;
if(mat[i][j]=='R')
{
up[i][j]=;
lef[i][j]=;//这里设它为零,避免对后面的取值产生影响
l=j; //同时也无需担心会对ans取值产生影响,因为up(i,j)为零
}
else
{
if(i==) lef[i][j]=l+;
else
lef[i][j]=max(lef[i-][j],l+);
}
}
int r=n+;
for(int j=n;j>=;j--)
{
if(mat[i][j]=='R')
{
r=j;
righ[i][j]=n+;
}
else
{
if(i==) righ[i][j]=r-;
else
righ[i][j]=min(righ[i-][j],r-);
}
}
}
} void Print()
{
int ans=;
for(int i=;i<=m;i++)
for(int j=;j<=n;j++)
{
ans=max(ans,*(righ[i][j]-lef[i][j]+)*up[i][j]);
}
cout<<ans<<endl;
} int main()
{
int T;
cin>>T;
while(T--)
{
Init();
Work();
Print();
}
return ;
}
最新文章
- 【bzoj4008】 HNOI2015—亚瑟王
- C++各种进制的转换
- js-JavaScript高级程序设计学习笔记9
- 与你相遇好幸运,Sail.js其他字段查询
- 微信开发那点事(No.001)
- 旧文&mdash;冬日感怀
- seajs集成jquery的一个坑
- 解决IE11出现异常SCRIPT5011:不能执行已释放Script的代码
- iOS 进阶 第十四天(0416)
- JS面向对象笔记二
- SpringBoot学习之Json数据交互
- [翻译]简单的实现一个Promise
- 【Unity Shaders】Mobile Shader Adjustment—— 什么是高效的Shader
- Javascript高级编程学习笔记(85)—— Canvas(2)2D上下文
- phpmyadmin低权限getshell
- 快速简单搭建wordpress平台
- 章节二、4-String以及StringBuffer和StringBuilder的对比
- 【Teradata】四舍五入函数
- Serlect的笔记二(request 、 ersponse)
- Jquery :animate反复执行的动画可以利用函数的回调
热门文章
- 【170】◀▶ IDL 学习初体验-全
- ViewModel、ViewData、ViewBag、TempData、Session之间的区别和各自的使用方法
- 双栈排序 2008年NOIP全国联赛提高组(二分图染色)
- Ubuntu服务器WDCP可视化界面搭建注意
- Uva 10766 Organising the Organisation (Matrix_tree 生成树计数)
- EditText(7)EditText输入事件监听
- Android 性能优化(13)网络优化( 9)Determining and Monitoring the Docking State and Type
- UML中类之间的关系
- Hive insert into directory 命令输出的文件没有列分隔符分析和解决
- json常识