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 ;
}

最新文章

  1. 【bzoj4008】 HNOI2015—亚瑟王
  2. C++各种进制的转换
  3. js-JavaScript高级程序设计学习笔记9
  4. 与你相遇好幸运,Sail.js其他字段查询
  5. 微信开发那点事(No.001)
  6. 旧文&mdash;冬日感怀
  7. seajs集成jquery的一个坑
  8. 解决IE11出现异常SCRIPT5011:不能执行已释放Script的代码
  9. iOS 进阶 第十四天(0416)
  10. JS面向对象笔记二
  11. SpringBoot学习之Json数据交互
  12. [翻译]简单的实现一个Promise
  13. 【Unity Shaders】Mobile Shader Adjustment—— 什么是高效的Shader
  14. Javascript高级编程学习笔记(85)—— Canvas(2)2D上下文
  15. phpmyadmin低权限getshell
  16. 快速简单搭建wordpress平台
  17. 章节二、4-String以及StringBuffer和StringBuilder的对比
  18. 【Teradata】四舍五入函数
  19. Serlect的笔记二(request 、 ersponse)
  20. Jquery :animate反复执行的动画可以利用函数的回调

热门文章

  1. 【170】◀▶ IDL 学习初体验-全
  2. ViewModel、ViewData、ViewBag、TempData、Session之间的区别和各自的使用方法
  3. 双栈排序 2008年NOIP全国联赛提高组(二分图染色)
  4. Ubuntu服务器WDCP可视化界面搭建注意
  5. Uva 10766 Organising the Organisation (Matrix_tree 生成树计数)
  6. EditText(7)EditText输入事件监听
  7. Android 性能优化(13)网络优化( 9)Determining and Monitoring the Docking State and Type
  8. UML中类之间的关系
  9. Hive insert into directory 命令输出的文件没有列分隔符分析和解决
  10. json常识