首页 > 其他分享 >单调栈学习笔记

单调栈学习笔记

时间:2023-11-08 19:33:42浏览次数:39  
标签:int top 笔记 学习 ++ ans kuan 单调

今天模拟赛 B 没想出来,甚至没到单调栈那一步。到了可能也不会做。

发现单调栈已经忘干净了,之前学过的悬线法也不太会,这里补一下单调栈。

板子:HISTOGRA - Largest Rectangle in a Histogram

在我的这篇博客里有题解。总之我自己是看懂了的。


单调栈求最大全 1 子矩阵问题

P4147 玉蟾宫

思路同上,只是枚举行,对于每一行处理列最往上能扩展多少作为该位置的高度,将其转换为当前行上的上述问题。

不要忘了清空 top,以及每次需要多建一个位置处理最后栈中剩余。

#include<bits/stdc++.h>
using namespace std;
const int N=1010;
int n,m;
int ans;
int a[N][N];
int top,s[N],w[N],b[N];
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++){
			char c;
			scanf("%s",&c);
			if(c=='F') a[i][j]=1;
			else a[i][j]=0;
		}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			if((a[i][j]==a[i-1][j]||i==1)&&a[i][j]) b[j]++;
			else if(a[i][j]) b[j]=1;
			else b[j]=0;
		}
		top=0;
		b[m+1]=0;
		for(int j=1;j<=m+1;j++){
			if(b[j]>s[top]){s[++top]=b[j];w[top]=1;continue;}
			int kuan=0;
			while(s[top]>b[j]){
				kuan+=w[top];
				ans=max(ans,kuan*s[top]);
				top--;
			}
			s[++top]=b[j];
			w[top]=kuan+1;
		}
	}
	printf("%d",ans*3);
}

标签:int,top,笔记,学习,++,ans,kuan,单调
From: https://www.cnblogs.com/Moyyer-suiy/p/17818126.html

相关文章

  • 11/8训练笔记
    P6273[eJOI2017]魔法题解考虑定义\(S_{r_k}=\Sigma_{i=1}^{r}[s_i=k]\),那么对于任意一个子串\([l,r]\),其为有魔法的子串的充要条件为\(S_{c_{r}}-S_{c_{l-1}}\)对于任意的,在\(s\)中出现了的\(c\)为定值。任取一个在\(s\)中出现了的字符\(A\),那么上述充要条件可转换......
  • electron+vite笔记
    1、配置国内electron 镜像   .npmrc   electron_mirror=https://registry.npmmirror.com/-/binary/electron/  electron_builder_binaries_mirror=https://registry.npmmirror.com/-/binary/electron-builder-binaries/2、创建vite项目    pnpmcreate......
  • C++笔记 -- 使用STL的function实现回调机制(回调函数)
    1.使用普通函数示例一 代码:#include<iostream>#include<functional>//定义一个回调函数类型usingCallback=std::function<void(int)>;//定义一个函数,用于演示回调函数的使用voidperformOperation(intdata,Callbackcallback){//执......
  • 世界上最全面的elasticsearch学习之路,祝你早日学成归来
    开胃菜,核心知识篇elasticsearch安装和使用elasticsearch索引curd,mapping映射,queryDSLelasticsearch分词器characterfilter,tokenizer,tokenfilter elasticsearch聚合查询Elasticsearch-直观了解查询(term、match、match_phrase和query_string)区别ES搜索(con......
  • kafka第二天学习笔记
    第二天学习Kafka,我们继续深入了解这个分布式流处理平台的核心概念和功能。以下是一些重要的知识点和概念:Kafka的消费者组:消费者组是多个消费者实例的组合,可以共同消费一个topic中的消息。消费者组中的每个消费者会均匀分配topic中的消息,实现负载均衡和高可用性。Kafka的分区策略:当......
  • 11.8读书笔记《需求掌握过程》02
    所谓需求,就是那些必须在开始进行产品构建前发现的东西,如果在构建的过程中才发现需求,或者更晚更糟,直至客户已经在使用产品的时候才发现需求,那么代价将会是很大的,效率也将十分低下。《掌握需求过程》这本书中,讲述了身为一个需求分析师,应完成的几个工作内容。按书中所说,分析师即......
  • Python学习心得
     1.学习资源:2.开始学习Python之前,选择一些适合初学者的学习资源,如在线教程、教科书和视频课程。一些常用的学习资源包括Python官方文档、Coursera、edX、Udemy等在线学习平台。3.安装和环境设置:4.安装Python解释器。你可以从Python官方网站下载最新的Python版本,并按照官方文......
  • C#winform学习2
    1.在工具栏中实现以下效果工具箱-->菜单和工具栏-->ToolStrip,拖拽进来后,选择button,右键DisplayStyle-->ImageAndText然后再在属性中修改文本为员工查询 2.进度一:完成页面以及基础的页面连接 ......
  • 机器学习——网络中的网络NiN
    NiN块回想一下,卷积层的输入和输出由四维张量组成,张量的每个轴分别对应样本、通道、高度和宽度。另外,全连接层的输入和输出通常是分别对应于样本和特征的二维张量。NiN的想法是在每个像素位置(针对每个高度和宽度)应用一个全连接层。如果我们将权重连接到每个空间位置,我们可以将......
  • Dart 基础知识笔记
    本文主要介绍Dart基础知识笔记。tourmain()函数是Dart程序的入口main()函数返回void并具有可选的List<String>参数作为参数所有对象都从Object类继承Dart是强类型当您想明确地不希望有任何类型时,使用特殊类型dynamicDart可以在函数内创建函数(嵌套函数或局部函数),可......