蓝桥杯算法题:栈(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的二次开发能力,可以有效集成并强化物流管理系统的数据处理与通信功能,…...
谷歌浏览器插件
项目中有时候会用到插件 sync-cookie-extension1.0.0:开发环境同步测试 cookie 至 localhost,便于本地请求服务携带 cookie 参考地址:https://juejin.cn/post/7139354571712757767 里面有源码下载下来,加在到扩展即可使用FeHelp…...
深入浅出Asp.Net Core MVC应用开发系列-AspNetCore中的日志记录
ASP.NET Core 是一个跨平台的开源框架,用于在 Windows、macOS 或 Linux 上生成基于云的新式 Web 应用。 ASP.NET Core 中的日志记录 .NET 通过 ILogger API 支持高性能结构化日志记录,以帮助监视应用程序行为和诊断问题。 可以通过配置不同的记录提供程…...
Oracle查询表空间大小
1 查询数据库中所有的表空间以及表空间所占空间的大小 SELECTtablespace_name,sum( bytes ) / 1024 / 1024 FROMdba_data_files GROUP BYtablespace_name; 2 Oracle查询表空间大小及每个表所占空间的大小 SELECTtablespace_name,file_id,file_name,round( bytes / ( 1024 …...
oracle与MySQL数据库之间数据同步的技术要点
Oracle与MySQL数据库之间的数据同步是一个涉及多个技术要点的复杂任务。由于Oracle和MySQL的架构差异,它们的数据同步要求既要保持数据的准确性和一致性,又要处理好性能问题。以下是一些主要的技术要点: 数据结构差异 数据类型差异ÿ…...
04-初识css
一、css样式引入 1.1.内部样式 <div style"width: 100px;"></div>1.2.外部样式 1.2.1.外部样式1 <style>.aa {width: 100px;} </style> <div class"aa"></div>1.2.2.外部样式2 <!-- rel内表面引入的是style样…...
在web-view 加载的本地及远程HTML中调用uniapp的API及网页和vue页面是如何通讯的?
uni-app 中 Web-view 与 Vue 页面的通讯机制详解 一、Web-view 简介 Web-view 是 uni-app 提供的一个重要组件,用于在原生应用中加载 HTML 页面: 支持加载本地 HTML 文件支持加载远程 HTML 页面实现 Web 与原生的双向通讯可用于嵌入第三方网页或 H5 应…...
中医有效性探讨
文章目录 西医是如何发展到以生物化学为药理基础的现代医学?传统医学奠基期(远古 - 17 世纪)近代医学转型期(17 世纪 - 19 世纪末)现代医学成熟期(20世纪至今) 中医的源远流长和一脉相承远古至…...
使用Spring AI和MCP协议构建图片搜索服务
目录 使用Spring AI和MCP协议构建图片搜索服务 引言 技术栈概览 项目架构设计 架构图 服务端开发 1. 创建Spring Boot项目 2. 实现图片搜索工具 3. 配置传输模式 Stdio模式(本地调用) SSE模式(远程调用) 4. 注册工具提…...
【笔记】WSL 中 Rust 安装与测试完整记录
#工作记录 WSL 中 Rust 安装与测试完整记录 1. 运行环境 系统:Ubuntu 24.04 LTS (WSL2)架构:x86_64 (GNU/Linux)Rust 版本:rustc 1.87.0 (2025-05-09)Cargo 版本:cargo 1.87.0 (2025-05-06) 2. 安装 Rust 2.1 使用 Rust 官方安…...
vulnyx Blogger writeup
信息收集 arp-scan nmap 获取userFlag 上web看看 一个默认的页面,gobuster扫一下目录 可以看到扫出的目录中得到了一个有价值的目录/wordpress,说明目标所使用的cms是wordpress,访问http://192.168.43.213/wordpress/然后查看源码能看到 这…...
