BZOJ 3039: 玉蟾宫
2024-10-15 12:26:23
3039: 玉蟾宫
Description
有一天,小猫rainbow和freda来到了湘西张家界的天门山玉蟾宫,玉蟾宫宫主蓝兔盛情地款待了它们,并赐予它们一片土地。
这片土地被分成N*M个格子,每个格子里写着'R'或者'F',R代表这块土地被赐予了rainbow,F代表这块土地被赐予了freda。
现在freda要在这里卖萌。。。它要找一块矩形土地,要求这片土地都标着'F'并且面积最大。
但是rainbow和freda的OI水平都弱爆了,找不出这块土地,而蓝兔也想看freda卖萌(她显然是不会编程的……),所以它们决定,如果你找到的土地面积为S,它们每人给你S两银子。
Input
第一行两个整数N,M,表示矩形土地有N行M列。
接下来N行,每行M个用空格隔开的字符'F'或'R',描述了矩形土地。
Output
输出一个整数,表示你能得到多少银子,即(3*最大'F'矩形土地面积)的值。
Sample Input
5 6
R F F F F F
F F F F F F
R R R F F F
F F F F F F
F F F F F F
Sample Output
45
——我是愉快的分隔符——
这道题很明显一下子想到一个N^2M的算法,发现超时【BZOJ的题目呀…阿喂!
然后发现数据具有单调性,使用单调队列优化寻找最大矩形,NM时间复杂度,ACCEPT!
然后发现数据具有单调性,使用单调队列优化寻找最大矩形,NM时间复杂度,ACCEPT!
下面是代码:
#include<cstdio>
using namespace std;
int map[1010][1010];
int num[1010],len[1010];
int n,m;
char x[1];
int ans;
inline int remax(int a,int b){
return a>b?a:b;
}
int main(){
scanf("%d%d",&n,&m);
for (int i=1;i<=n;i++){
for (int j=1;j<=m;j++){
scanf("%s",&x);
if (x[0]=='F') map[i][j]=map[i-1][j]+1;
}
}
int maxs=0;
int length=0;
int top=0;
for (int i=1;i<=n;i++){
top=0;
num[top]=len[top]=0;
for (int j=1;j<=m;j++){
if (map[i][j]>=num[top]){
top++;
num[top]=map[i][j];
len[top]=1;
}else{
length=0;
while(top&&map[i][j]<num[top]){
length+=len[top];
maxs=remax(maxs,length*num[top]);
--top;
}
top++;
num[top]=map[i][j];
len[top]=length+1;
}
}
length=0;
for (int j=top;j>=1;j--){
length+=len[j];
maxs=remax(maxs,length*num[j]);
}
}
int ans=maxs*3;
printf("%d\n",ans);
return 0;
}
最新文章
- 面向对象(五)super
- nodejs开发指南demo
- db2look和db2move详解
- 在MFC中使用GDI+的一般方法,以VC6.0编译器为例
- 巧用在线html编辑器,保存文章到数据库(带html标签)
- Atitit.atiInputMethod&#160;v2词库清理策略工具&#160;&#160;&#160;&#160;q229
- POJ3020Antenna Placement(最小路径覆盖+重在构图)
- OC:属性、点语法、KVC
- Matlab编程-数值计算相关语法
- [论文阅读]Going deeper with convolutions(GoogLeNet)
- 学习Selenium遇到的问题和解决方案
- luogu1919 A*BProblem升级版 (FFT)
- java框架之SpringMVC(1)-入门&;整合MyBatis
- C++STL中的unique函数解析
- js setInterval参数设置
- 在使用Git提交代码的时候犯了个低级错误
- QDesktopWidget
- ubuntu下使用python3的有些库时,解决";raise ImportError(str(msg) + &#39;, please install the python3-tk package&#39;) ImportError: No module named &#39;_tkinter&#39;, please install the python3-tk package";的错误
- java编程的一些注意事项
- Unity脚本中各函数成员的生命周期