蓝桥杯算法题:栈(Stack)



这道题考的是递推动态规划,可能不是很难,不过这是自己第一次靠自己想出状态转移方程,所以纪念一下:
要做这些题目,首先要把题目中会出现什么状态给找出来,然后想想他们的状态可以通过什么操作转移,进而写出状态转移方程
这道题的状态可以分为三个,一个是已输出序列,另一个是栈中序列,另一个是未输入序列,那有什么操作可以改变序列呢,有两个,操作一是未输入序列往栈中放数字,操作二是栈中序列把数字输出到已输出序列。这时设置一数组f[i][j][k],i表示已输出序列长度,j表示栈中序列长度,k表示未输入序列的长度,则可以根据红字的操作写出状态转移方程:f[i][j][k]=f[i][j-1][k+1]+f[i-1][j+1][k];
其中[i][j-1][k+1]变为f[i][j][k]表示操作一,f[i-1][j+1][k]变成f[i][j][k]表示操作二(注意有些状态只能由一个操作转换而来,不然就发生不可能的情况,即越界)比如说{2,0,1}只能由状态{1,1,1}转变而来,不能由{2,-1,2}转变而来
#include<bits/stdc++.h>
using namespace std;
int f[20][20][20];
int main(){int n;cin>>n;for(int i=0;i<=n;i++){f[0][i][n-i]=1;f[i][0][n-i]=1;//这两种情况,栈里数的顺序是唯一的,所以个数也就为1}for(int i=1;i<=n;i++){for(int j=0;j<=n;j++){for(int k=0;k<=n;k++){if(i+j+k==n){if(j==n&&k<=n-1)f[i][j][k]=f[i][j-1][k+1];else if(j==0||k==n)f[i][j][k]=f[i-1][j+1][k];else f[i][j][k]=f[i-1][j+1][k]+f[i][j-1][k+1];}}}} cout<<f[n][0][0]<<endl;
}
不过我又去看了别人的题解,似乎更好,又学到了,其实我也想过用一个数的位置来看状态,不过没能想得那么利索

相关文章:
蓝桥杯算法题:栈(Stack)
这道题考的是递推动态规划,可能不是很难,不过这是自己第一次靠自己想出状态转移方程,所以纪念一下: 要做这些题目,首先要把题目中会出现什么状态给找出来,然后想想他们的状态可以通过什么操作转移…...
JavaWeb-监听器
文章目录 1.基本介绍2.ServletContextListener1.基本介绍2.创建maven项目,导入依赖3.代码演示1.实现ServletContextListener接口2.配置web.xml3.结果 3.ServletContextAttributeListener监听器1.基本介绍2.代码实例1.ServletContextAttributeListener.java2.配置web…...
系统架构设计基础知识
一. 系统架构概述系统架构的定义 系统架构(System Architecture)是系统的一种整体的高层次的结构表示,是系统的骨架和根基,支撑和链接各个部分,包括构件、连接件、约束规范以及指导这些内容设计与演化的原理࿰…...
Vue自定义指令介绍及使用方法
介绍 除了 Vue 内置的一系列指令 (比如 v-model 或 v-show) 之外,Vue 还允许你注册自定义的指令 (Custom Directives)。 之前已经介绍了两种在 Vue 中重用代码的方式:组件 和 组合式函数。组件是主要的构建模块,而组合式函数则侧重于有状态…...
React 组件生命周期函数的用法和示例代码
React 中的生命周期函数可以分为三个阶段:Mounting(挂载),Updating(更新)和 Unmounting(卸载)。每个阶段都有不同的函数,用于执行不同的操作。 Mounting(挂载…...
【nginx运维】[emerg]: bind() to 0.0.0.0:80 failed (98: Address already in use)
关于nginx端口被占用的问题: If you get following error, when you try to start nginx… [emerg]: bind() to 0.0.0.0:80 failed (98: Address already in use) Then it means nginx or some other process is already using port 80. You can kill it using: su…...
浏览器工作原理与实践--虚拟DOM:虚拟DOM和实际的DOM有何不同
虚拟DOM是最近非常火的技术,两大著名前端框架React和Vue都使用了虚拟DOM,所以我觉得非常有必要结合浏览器的工作机制对虚拟DOM进行一次分析。当然了,React和Vue框架本身所蕴含的知识点非常多,而且也不是我们专栏的重点,…...
arm工作模式、arm9通用寄存器、异常向量表中irq的异常向量、cpsr中的哪几位是用来设置工作模式以及r13,r14,15别名是什么?有什么作用?
ARM 首先先介绍一下ARM公司。 ARM成立于1990年11月,前身为Acorn计算机公司 主要设计ARM系列RISC处理器内核 授权ARM内核给生产和销售半导体的合作伙伴ARM公司不生产芯片 提供基于ARM架构的开发设计技术软件工具评估版调试工具应用软件总线架构外围设备单元等等CPU中…...
电脑上音频太多,播放速度又不一致,如何批量调节音频播放速度?
批量调节音频速度是现代音频处理中的一个重要环节,尤其在音乐制作、电影剪辑、有声书制作等领域,它能够帮助制作者快速高效地调整音频的播放速度,从而满足特定的制作需求。本文将详细介绍批量调节音频速度的方法、技巧和注意事项,…...
pe格式从入门到图形化显示(十)-扩展最后一个节
文章目录 前言一、怎么扩展最后一个节?二、扩大节1.扩展节2.保存文件 前言 通过分析和解析Windows PE格式,并使用qt进行图形化显示 一、怎么扩展最后一个节? 在PE文件中,扩大最后一个节通常是通过修改PE文件头中的节表来实现的。…...
设计模式之创建型模式---建造者模式
文章目录 建造者模式概述经典的建造者模式建造者模式的变种总结 建造者模式概述 建造者模式是一种广泛使用的设计模式,在三方开源库和各种SDK中经常见到。建造者设计模式在四人帮的经典著作《设计模式:可复用面向对象软件基础》中被提及,它的…...
如何从零开始训练一个语言模型
如何从零开始训练一个语言模型 #mermaid-svg-gtUlIrFtNPw1oV5a {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-gtUlIrFtNPw1oV5a .error-icon{fill:#552222;}#mermaid-svg-gtUlIrFtNPw1oV5a .error-text{fill:#5522…...
Python 设计一个监督自己的软件1
基本要求:每做一件事,软件就会按照事情权重加相应的分数,总分数也会增加,要可视化页面 使用Python编写的一个简单的日常任务记录和评分系统,包括可视化页面。 首先,我们定义一个任务字典,其中包含各种日常任务及其对应的权重分数…...
商家转账到零钱权限开通操作攻略
商家转账到零钱是什么? 商家转账到零钱是微信商户号里的一个功能,很早以前叫企业付款到零钱。 从2022年5月18日,原“企业付款到零钱”升级为“商家转账到零钱”,已开通商户的功能使用暂不受影响,新开通商户可前往「产…...
【DAC‘ 2022】Kite: A Family of Heterogeneous Interposer Topologies
Kite: A Family of Heterogeneous Interposer Topologies Enabled via Accurate Interconnect Modeling 背景和动机 背景动机 工作内容 KITE 拓扑 实验方法和评估结果 Kite: A Family of Heterogeneous Interposer Topologies Enabled via Accurate Interconnect Modeling 通…...
数据结构—堆
什么是堆 堆是一种特殊的树形结构,其中每个节点都有一个值。堆可以分为两种类型:最大堆和最小堆。在最大堆中,每个节点的值都大于等于其子节点的值;而在最小堆中,每个节点的值都小于等于其子节点的值。这种特性使得堆…...
Kubernetes学习笔记8
Kubernetes集群客户端工具kubectl 我们已经能够部署Kubernetes了,那么我们如何使用Kubernetes集群运行企业的应用程序呢?那么,我们就需要使用命令行工具kubectl。 kubectl就是控制Kubernetes的驾驶舱,它允许你执行所有可能的Kube…...
[渗透利器]在线渗透测试工具箱?测评
前言 hxd更新完了在线工具箱,受邀写一下使用体验以及测评 使用体验 这个工具箱设计的比较轻便,以往用过的工具箱大多都是以离线打包的方式发布,该工具箱,作者自己掏钱自己买服务器,自己买带宽,先生大义。…...
rocketmq和rabbitmq总是分不清?
1. 官方解答 摘自百度搜索: 2. 通俗易懂的回答...
利用Python ARM网关仓储物流AGV小车控制器
在现代智慧物流体系中,高效的信息管理系统是物流中心实现精准跟踪货物、科学管理库存及优化配送路线的关键环节。通过采用ARM架构的工控机或网关,并结合Python的二次开发能力,可以有效集成并强化物流管理系统的数据处理与通信功能,…...
《Qt C++ 与 OpenCV:解锁视频播放程序设计的奥秘》
引言:探索视频播放程序设计之旅 在当今数字化时代,多媒体应用已渗透到我们生活的方方面面,从日常的视频娱乐到专业的视频监控、视频会议系统,视频播放程序作为多媒体应用的核心组成部分,扮演着至关重要的角色。无论是在个人电脑、移动设备还是智能电视等平台上,用户都期望…...
Qt Widget类解析与代码注释
#include "widget.h" #include "ui_widget.h"Widget::Widget(QWidget *parent): QWidget(parent), ui(new Ui::Widget) {ui->setupUi(this); }Widget::~Widget() {delete ui; }//解释这串代码,写上注释 当然可以!这段代码是 Qt …...
高危文件识别的常用算法:原理、应用与企业场景
高危文件识别的常用算法:原理、应用与企业场景 高危文件识别旨在检测可能导致安全威胁的文件,如包含恶意代码、敏感数据或欺诈内容的文档,在企业协同办公环境中(如Teams、Google Workspace)尤为重要。结合大模型技术&…...
ElasticSearch搜索引擎之倒排索引及其底层算法
文章目录 一、搜索引擎1、什么是搜索引擎?2、搜索引擎的分类3、常用的搜索引擎4、搜索引擎的特点二、倒排索引1、简介2、为什么倒排索引不用B+树1.创建时间长,文件大。2.其次,树深,IO次数可怕。3.索引可能会失效。4.精准度差。三. 倒排索引四、算法1、Term Index的算法2、 …...
PL0语法,分析器实现!
简介 PL/0 是一种简单的编程语言,通常用于教学编译原理。它的语法结构清晰,功能包括常量定义、变量声明、过程(子程序)定义以及基本的控制结构(如条件语句和循环语句)。 PL/0 语法规范 PL/0 是一种教学用的小型编程语言,由 Niklaus Wirth 设计,用于展示编译原理的核…...
【服务器压力测试】本地PC电脑作为服务器运行时出现卡顿和资源紧张(Windows/Linux)
要让本地PC电脑作为服务器运行时出现卡顿和资源紧张的情况,可以通过以下几种方式模拟或触发: 1. 增加CPU负载 运行大量计算密集型任务,例如: 使用多线程循环执行复杂计算(如数学运算、加密解密等)。运行图…...
NFT模式:数字资产确权与链游经济系统构建
NFT模式:数字资产确权与链游经济系统构建 ——从技术架构到可持续生态的范式革命 一、确权技术革新:构建可信数字资产基石 1. 区块链底层架构的进化 跨链互操作协议:基于LayerZero协议实现以太坊、Solana等公链资产互通,通过零知…...
06 Deep learning神经网络编程基础 激活函数 --吴恩达
深度学习激活函数详解 一、核心作用 引入非线性:使神经网络可学习复杂模式控制输出范围:如Sigmoid将输出限制在(0,1)梯度传递:影响反向传播的稳定性二、常见类型及数学表达 Sigmoid σ ( x ) = 1 1 +...
(一)单例模式
一、前言 单例模式属于六大创建型模式,即在软件设计过程中,主要关注创建对象的结果,并不关心创建对象的过程及细节。创建型设计模式将类对象的实例化过程进行抽象化接口设计,从而隐藏了类对象的实例是如何被创建的,封装了软件系统使用的具体对象类型。 六大创建型模式包括…...
Proxmox Mail Gateway安装指南:从零开始配置高效邮件过滤系统
💝💝💝欢迎莅临我的博客,很高兴能够在这里和您见面!希望您在这里可以感受到一份轻松愉快的氛围,不仅可以获得有趣的内容和知识,也可以畅所欲言、分享您的想法和见解。 推荐:「storms…...
