P4147玉蟾宫——最大子矩阵
2024-09-08 18:50:58
悬线法裸题。
代码如下:
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int const MAXN=,MAXM=;
int n,m,lf[MAXN][MAXM],rt[MAXN][MAXM],ans,a[MAXN][MAXM],sta[MAXM],top;
bool d[MAXN][MAXM];
int main()
{
scanf("%d%d",&n,&m);
char dc;
for(int i=;i<=n;i++)
for(int j=;j<=m;j++)
{
cin>>dc;
if(dc=='R')d[i][j]=;
else
{
for(int k=i-;k;k--)
if(d[k][j])
{
a[i][j]=i-k;
break;
}
if(!a[i][j])a[i][j]=i;
// printf("a[%d][%d]=%d\n",i,j,a[i][j]);
}
}
for(int i=;i<=n;i++)
{
memset(sta,,sizeof sta);
top=;
for(int j=;j<=m;j++)
{
while(a[i][j]<=a[i][sta[top]]&&top)top--;
lf[i][j]=sta[top];
sta[++top]=j;
}
memset(sta,,sizeof sta);
top=;sta[top]=m+;
for(int j=m;j;j--)
{
while(a[i][j]<=a[i][sta[top]]&&top)top--;
rt[i][j]=sta[top];
sta[++top]=j;
}
// for(int j=1;j<=m;j++)
// printf("lf[%d][%d]=%d rt[%d][%d]=%d\n",i,j,lf[i][j],i,j,rt[i][j]);
}
for(int i=;i<=n;i++)
for(int j=;j<=m;j++)
{
int l,r;
if(d[i][j])continue;
if(!d[i][j]&&i>)
{
l=max(lf[i][j],lf[i-][j]);
r=min(rt[i][j],rt[i-][j]);
ans=max(ans,a[i][j]*(r-l-));
}
else ans=max(ans,rt[i][j]-lf[i][j]-);
}
printf("%d",*ans);
return ;
}
最新文章
- 【转译】加入ZigBee联盟,共画物联网的未来
- apache安装mod_deflate配置支持gzip
- 做NavMesh相关工作时收集的一些文章
- 那些在学习iOS开发前就应该知道的事(part 2)
- Java Hour 22 I/O
- backbonejs中的集合篇(一)
- 淘宝主搜索离线集群完成Hadoop 2
- hdu 3544 Alice&#39;s Game 博弈论
- Android 动画之RotateAnimation应用详解
- git将本地项目添加到github远程仓库
- Spring学习之注入方式
- NSThread的一些细节
- hdu4055 Number String
- 访问量分类统计(QQ,微信,微博,网页,网站APP,其他)
- maven(项目管理工具系列 maven 总结二)
- 区间(interval)
- ACM Wooden Stricks
- Ubuntu server 16.04的安装 以及配置(服务器版)
- Modification Default Identity Table
- Bootstrap Web框架
热门文章
- Kermit,Xmodem,1K-Xmodem,Ymodem,Zmodem传输协议小结
- HttpClient通过Post方式发送Json数据
- Android中Environment与StatFs获取系统/SDCard存储空间大小
- ok6410[002] ubuntu1604系统下搭配ckermit和dnw基于RAM的裸机程序调试环境
- cygwin配置个人环境,android模拟器root映象和Babun
- Java爬虫快速开发工具uncs的部署攻略
- 总结一下vue调试的方法
- Java链接MySql数据库(转)
- EasyDarwin开源团队招募开发组成员
- cocos2d-js v3新特性