2018.09.29 bzoj3039: 玉蟾宫(悬线法)
2024-09-11 23:08:00
传送门
悬线法的板子题。
悬线法只需要保存当期点向下最多多少个,把这个当成一条线,再处理出线绷直之后最多能向左右延展多少就行了。
代码:
#include<bits/stdc++.h>
#define N 1005
using namespace std;
int n,m,a[N][N],L[N][N],R[N][N],h[N][N],ans=0;
char s[3];
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;++i)for(int j=1;j<=m;++j){
scanf("%s",s),h[i][j]=1,L[i][j]=R[i][j]=j;
if(s[0]=='F')a[i][j]=1;
}
for(int i=1;i<=n;++i)for(int j=2;j<=m;++j)if(a[i][j]&a[i][j-1])L[i][j]=L[i][j-1];
for(int i=1;i<=n;++i)for(int j=m-1;j;--j)if(a[i][j]&a[i][j+1])R[i][j]=R[i][j+1];
for(int i=1;i<=n;++i)for(int j=1;j<=m;++j){
if((i^1)&&(a[i][j]&a[i-1][j])){
L[i][j]=max(L[i][j],L[i-1][j]),R[i][j]=min(R[i][j],R[i-1][j]);
h[i][j]=h[i-1][j]+1;
}
ans=max(ans,a[i][j]*(R[i][j]-L[i][j]+1)*h[i][j]);
}
printf("%d",ans*3);
return 0;
}
最新文章
- xml文件解析(解析以后在RootTableViewController输出)
- JavaScript面向对象的程序设计
- VS2015链接错误一则
- spring @value 注入static
- tomcat的下载安装和配置以及和eclipse的配置
- 黑马程序员——OC语言 三大特性之继承
- Java并发编程:阻塞队列(转载)
- HW—可怕的阶乘n!__注意大数据函数的使用BigInteger
- Linux学习新篇——常用命令和快捷键总结
- jQuery绑定事件的四种基本方式
- Linux常用命令汇总及使用方法(一)
- 使用StyleCop.Analyzers进行代码审查
- 黑科技:纯CSS定制文本省略
- java语言环境jdk的安装和环境变量的配置
- Java-ServletRequestEvent-ServletRequestAttributeEvent
- PostgreSQL:安装及中文显示
- Stream、FileStream、MemoryStream的区别
- Potplayer播放器使用笔记
- 二叉查找树及B-树、B+树、B*树变体
- CF 449D 题解(状压+容斥)
热门文章
- spring_cxf_basic_sender
- UI5-文档-4.17-Fragment Callbacks
- Kotlin语言学习笔记(6)
- sessionStorage和localStorage
- 基于JS的文本验证
- DEXSeq
- Nexus 使用配置
- 一个团队和他们的调查表-----(";调查表与调查结果分析";心得体会)
- Jiu Yuan Wants to Eat(树链剖分+线段树延迟标记)
- python进程之间修改数据[Manager]与进程池[Pool]