栈 - Problem Solution - 菜鸟OJ

0
黑白铅笔 SU @ 2024-7-14 12:53:13

以出栈序列中数字 $1$ 的位置为基准，将出栈序列分为前后两部分。前半部分可以看成若干个数进行同样过程得到的序列，后半部分同理。

那么，设 $f(i)$ 表示 $i$ 个元素进行题目中描述的出入栈操作可能出现的输出序列总数。有:
$f(1)=1$ $$f(i) = f(0)f(i-1) + f(1)f(i-2) + \cdots + f(i-1)f(0)$$
递推计算即可，这是一个卡特兰数列。

ID

21

Time

1000ms

Memory

256MiB

Difficulty

(None)

Tags

# Submissions

Accepted

0

Uploaded By