当前位置: 首页 > news >正文

洛谷P1044 栈(学习向)

题面描述

P1044 [NOIP 2003 普及组] 栈 - 洛谷

解析

题解:P1044 [NOIP 2003 普及组] 栈 - 洛谷专栏

我采用的是上面这篇,这是dp的思路做法,当然也可以用dfs求解。

但是,dp身为职业选手和算法水赛混子的分水岭,这里的dp我就看不懂了

于是我画了张图去理解它(没错,写这篇其实我是想存我的杰作)

天赋树点不上了,那就学可视化吧!

通过画图,我也才理解到了这个dp公式的核心要义:

1.当x,y都不为0时

f(x,y)=f(x-1,y+1)+f(x,y)

这个的意思就是,当前的情况等于出栈一个数的情况和入栈一个数的情况之和。

2.当x为0时

f(x,y)=1

不论你的顺序是什么,也不论y等于几,也就是不论当前栈有多少个数,他的出栈顺序唯一。因为你的等待区已经没有数了。

3.当y为0且x不为0时

f(x,y)=f(x-1,y+1)

当前栈中没有元素,等待区还有x个元素,那么你只能做到把等待区的一个数压进来。

画图理解法万岁!(补药学算法,太难啦)

http://www.lryc.cn/news/583073.html

相关文章:

  • react16-react19都更新哪些内容?
  • clickhouse 各个引擎适用的场景
  • 【TCP/IP】2. 计算机网络与因特网体系结构
  • 手机文件夹隐藏工具,一键保护隐私
  • 数据库性能优化指南:解决ORDER BY导致的查询性能问题( SQL Server )
  • Dify 文本语意识别与自动补全工作流
  • MyBatisPlus-03-扩展功能
  • C#基础篇(11)泛型类与泛型方法详解
  • 1068.产品销售分析Ⅰ
  • huggingface 笔记: Trainer
  • 打造自己的组件库(二)CSS工程化方案
  • 跨服务sqlplus连接oracle数据库
  • 54页|PPT|新型数字政府综合解决方案:“一网 一云 一中台 N应用”平台体系 及“安全+运营”服务体系
  • 人工智能的基石:TensorFlow与PyTorch在图像识别和NLP中的应用
  • 影石(insta360)X4运动相机视频删除的恢复方法
  • 【视频观看系统】- 需求分析
  • 【DB2】load报错SQL3501W、SQL3109N、SQL2036N
  • Tensorflow的安装记录
  • django 一个表中包括id和parentid,如何通过parentid找到全部父爷id
  • react+ts 移动端页面分页,触底加载下一页
  • 板凳-------Mysql cookbook学习 (十一--------6)
  • 安卓设备信息查看器 - 源码编译
  • Android-重学kotlin(协程源码第二阶段)新学习总结
  • 中望CAD2026亮点速递(5):【相似查找】高效自动化识别定位
  • uniapp AndroidiOS 定位权限检查
  • Android ViewModel机制与底层原理详解
  • upload-labs靶场通关详解:第19关 条件竞争(二)
  • 池化思想-Mysql异步连接池
  • 5.注册中心横向对比:Nacos vs Eureka vs Consul —— 深度解析与科学选型指南
  • Web 前端框架选型:React、Vue 和 Angular 的对比与实践