洛谷P1044 栈(学习向)
题面描述
P1044 [NOIP 2003 普及组] 栈 - 洛谷
解析
题解:P1044 [NOIP 2003 普及组] 栈 - 洛谷专栏
我采用的是上面这篇,这是dp的思路做法,当然也可以用dfs求解。
但是,dp身为职业选手和算法水赛混子的分水岭,这里的dp我就看不懂了
于是我画了张图去理解它(没错,写这篇其实我是想存我的杰作)
天赋树点不上了,那就学可视化吧!
通过画图,我也才理解到了这个dp公式的核心要义:
1.当x,y都不为0时
这个的意思就是,当前的情况等于出栈一个数的情况和入栈一个数的情况之和。
2.当x为0时
不论你的顺序是什么,也不论y等于几,也就是不论当前栈有多少个数,他的出栈顺序唯一。因为你的等待区已经没有数了。
3.当y为0且x不为0时
当前栈中没有元素,等待区还有x个元素,那么你只能做到把等待区的一个数压进来。
画图理解法万岁!(补药学算法,太难啦)