【C++】栈的运用——卡特兰数_c++ 卡特兰数

$1,2,3,4$ 依次入栈，可能的出栈序列有多少种？

我们来模拟一下就知道了。

考虑 $4$ 最先出栈，那么就只有 $4321$ 这一种情况。

考虑 $3$ 最先出栈，那么 44 还没有入栈，栈中有 $1,2,3$ 那么出栈顺序有 $3214,3241,3421$ 三种情况。

考虑 $2$ 最先出栈，那么有 $2134,2143,2314,2341,2431$ 五种情况。

考虑 $1$ 最先出栈，那么有 $1234,1243,1324,1342,1432$ 五种情况。

总共有 $1+3+5+5=14$ 种情况。

公式一——直接计算

对于n个元素，一共有
$$\frac{1}{n+1}{C}_{2n}^n$$
种出栈顺序，这就是卡特兰数

公式二——递推

$f(n)$表示对于$n$个元素一共有$f(n)$种出栈序列情况
初始化$f[0]=f[1]=1$
$f\left(n\right)={\sum }_{i=1}^{n}f\left(i-1\right)f\left(n-i\right)$

本质上可以理解成一共有两种操作，权值为0

1. 权值加1
2. 权值减1
   一共进行$2n$次操作，操作过程中权值不小于0，并且操作结束后结果为0

例题

这道题的思路就是把每一个五元的人看作+1入栈，十元的人看作-1出栈，一共n个元素
按照卡特兰数直接求解即可

#include <bits/stdc++.h>
using namespace std;
long long ans=1,n;
int main() {
    cin >> n;
    for(long long i=n+1;i<=2*n;i++){
        ans*=i;
    }
    for(long long i=1;i<=n;i++){
        ans/=i;
    }
    cout<<ans/(n+1);
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14