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

P1044 [NOIP 2003 普及组] 栈

难度 算法s 日期 题目链接
普及− DP 2025-05-21 https://luogu.com.cn/problem/P1044

因为本人 DP 很差,故撰此文巩固一下。

本文是对 P1044 [NOIP 2003 普及组] 栈 题解 的详细解释。

写的很直白了。。。几乎没有理解难度吧。。。

DP 状态设计

二维 DP 做法,\(dp[x][y]\) 表示:

  • \(x\) 个元素未入栈,意味着可以入栈 \(x\) 次。
  • \(y\) 个元素在栈内,意味着可以出栈 \(y\) 次。

(注意这里没有明确 \(dp[...][...]\) 表示什么,只是设计了状态,下面讲怎么设计 \(dp[...][...]\) 要表示的值。)

将这样转移:

上图:“出入栈操作,状态转移过程”

然后呢?怎么算?

初始时,我们有一个状态 \(dp[n][0]\),也就是有 \(n\) 次入栈机会,但是从未执行过入栈操作。

接下来,我们进行操作, \(dp[x][y]\)\(x\)\(y\) 的值不断变化...

然后我们到达了一个末状态 \(dp[0][0]\),这时候我们没法进行更多操作了。

其实我们要计算的就是从初状态到末状态,有多少种“路径”,即所有可能的“操作序列”。

接下来我们要从末状态 \(Q\) 往回推,求可能的路径数。

很明显,从子状态 \(H\)\(I\) 到末状态 \(Q\) 都只有一条路径。(边界状态)

现在来看这三个点:\(A\)\(D\)\(E\)

很明显:

\(A\) 到末状态 \(Q\) 的路径数 \(=\) \(D\) 的路径数 \(+\) \(E\) 的路径数

归纳一下:

\(X\) 的路径数 \(=\) \(X\) 所有子状态的路径数之和

用这个公式从 \(Q\) 往回推,直到 \(P\) 就好了。

好,接下来DP。

决定了,\(dp[x][y]\) 就表示:还有 \(x\) 个元素要入栈,\(y\) 个元素要出栈,此时通向末状态可能的路径数。

(注意用词,这里用“还有...要”,暗示了最终要导向末状态 \(dp[0][0]\),必须把可以入栈的机会 \(x\) 和可以出栈的机会 \(y\) 都用完。)

一图以蔽之。

之前我们不是推了“出入栈操作,状态转移过程”吗,其实 DP 的方向就是恰好相反。

很容易得到状态转移公式:

\(dp[x][y]=dp[x-1][y+1]+dp[x][y-1]\)

从图中还可以看出,先沿 \(x\) 遍历,然后跳到下一列 \(y\)

代码(核心部分):

for (int x = 0; x <= n; x++) {for (int y = 0; y <= n; y++) {if (x == 0) {dp[x][y] = 1;} else if (y == 0) {dp[x][y] = dp[x - 1][y + 1];} else {dp[x][y] = dp[x][y - 1] + dp[x - 1][y + 1];}}}

[!important] 学到了什么?

对于这样一种问题:

给定初状态 \(P\)

可以进行 \(Op=\{...\}\) 种操作,每种操作会使当前状态转移到一个子状态。

求进行完所有操作后,可能的“操作路径”数。

那么我们用 DP 来解决问题,用反向推理的方法,其实 DP 转移方程很简单:

设计 DP 状态 \(dp(S)\)

\(S\) 为状态,应该要包含各种在操作过程中会变化的量,比如要入栈的次数啊等等,写出来就是 \((x,y)\) 这样的式子)

\(dp(S)=\sum_i dp(S_i)\)

其中 \(S_i\) 表示从 \(S\) 可以进行到的子状态。

http://www.hskmm.com/?act=detail&tid=25212

相关文章:

  • P1080 [NOIP 2012 提高组] 国王游戏
  • 音响没声音
  • P1654 OSU!
  • DynamoDB十年演进:云原生数据库的技术革新
  • 完整教程:MySQL全量、增量备份与恢复
  • 10/5
  • 10/4
  • 嵌入式MCU
  • porting perf性能观测工具
  • Windows常用快捷指令
  • Python 在金融中的应用- Part 1 - 教程
  • QBXT2025S刷题 Day4
  • java学习日记9.25
  • porting 开源memtester
  • 计算机的组成
  • 完整教程:用mediamtx搭建简易rtmp,rtsp视频服务器
  • oppoR9m MTK 6755 开启VCOM的9008模式
  • 关于电脑息屏后自动亮屏的的原因排查及解决方式
  • 机器人世界杯工业联赛技术解析
  • Squarepoint Challenge (Codeforces Round 1055, Div. 1 + Div. 2) A~E
  • k8s之基础概念
  • 251005
  • Java基础 Day26 - 详解
  • 14_mklink创建符号链接
  • 7_如何构建知识图谱
  • 点双连通分量例题:矿场搭建
  • MTK oppoR9m Smart Phone flash Tool 提示 ERROR: STATUS_UNSUPPORT_CTRL_CODE (0xC0010004)
  • 我开发的 Chrome 插件 SEO Tools Extension 今天上线了
  • Windows Server部署Vue3+Spring Boot项目 - 实践
  • 深入解析:阿里云无影云桌面深度测评