前言

其实卡特兰数跟很多东西都有联系（计算几何、递推等），且本题解较长，请耐心看完哦！题解求赞qwq

解题思路

1.暴力

看到题可以发现，本题可以模拟 pop（从栈顶弹出一个元素）和 push（将一个元素进栈）。

然后就 TLE 了（PS：我没有试过，但用正解算了 $n = 20$，然后肯定 TLE 的）

2.卡特兰数（Catalan）

现在讲讲正解。

注：定义 $C_n$ 为第 $n$ 个卡特兰数。

其中，$C_0 = C_1 = 1$。

先放一些卡特兰数：

$1，1，2，5，14，42，132，429，1430，4862$。

很显然，这是从 $C_0$ 到 $C_9$。

请注意，本题解的卡特兰数讲解是简单的版本，并且卡特兰数有很多种公式。

推导卡特兰数可用二叉树，我们想想：

• 用零个节点可以建几个不同的二叉树？
• $1$ 个（空二叉树也是树）

• 用一个节点可以建几个不同的二叉树？
• $1$ 个（可以自己画图，这里就不放图了）

• 用两个节点可以建几个不同的二叉树？
• $2$ 个（可以自己画图，这里就不放图了）

• 用三个节点可以建几个不同的二叉树？
• $5$ 个（可以自己画图，这里就不放图了）

• 用四个节点可以建几个不同的二叉树？
• $14$ 个（可以自己画图，这里就不放图了）

• 用五个节点可以建几个不同的二叉树？
• $42$ 个（可以自己画图，这里就不放图了）

可以发现，这里的的数就是卡特兰数！

然后我们充分发挥人类智慧！！！

可以得到：

$C_2 = 1 \times \frac{6}{3} = 1 \times 2 = 2$，

$C_3 = 2 \times \frac{10}{4} = 2 \times \frac{5}{2} = 5$，

$C_4 = 5 \times \frac{14}{5} = 14$，

就发现了真理：$C_n = C_{n-1} \times \frac{4n-2}{n+1}$。

然后你就 AC 了！

解题代码

#include <bits/stdc++.h>
using namespace std;

long long n, a[20] = {1, 1, 2, 5};

int main()
{
	cin >> n;
	for (long long i = 4; i <= n; i++) a[i] = a[i - 1] * (4 * i - 2) / (i + 1);
	cout << a[n] << endl;
	return 0;
 }

总结

这题其实有很多思路：

• 搜索；（不建议的，但也不是不可以）
• 分治，递推；（强推！！！）
• 打表。

根据$f(n-1) ~*~ \frac{4n~-~2}{n~+~1} = f(n)$写出的AC呆🐎:

#include <bits/stdc++.h>
using namespace std;
const int N = 20;

int n, a[N];

int main()
{
	cin >> n;
	a[0] = a[1] = 1;
	for (int i = 1; i <= n; i++)
	{
		a[i] = a[i - 1] * (((4 * i) - 2) / (double)(i + 1));
	}
	cout << a[n];
	
	return 0;
}

带计算过程版：

#include <bits/stdc++.h>
using namespace std;
const int N = 20;

int n, a[N];

int main()
{
	cin >> n;
	a[0] = a[1] = 1;
	for (int i = 1; i <= n; i++)
	{
		a[i] = (double)a[i - 1] * (double)((double)((4 * i) - 2) / (double)(i + 1));
		printf("\na[i - 1] * (((4 * i) - 2) / (i + 1))\n= %d * ((%d) - 2) / %d)\n= %d * (%d)\n= %d\n", a[i - 1], 4 * i, i + 1, a[i - 1], ((4 * i) - 2) / (i + 1), a[i - 1] * (((4 * i) - 2) / (i + 1)));
	}
	cout << a[n];
	
	return 0;
}