2003NOIP普及组真题 3. 栈

线上OJ 地址：

【03NOIP普及组】栈

核心思想

1、这类题目和火车进站出站是同一类问题，常规解法有两种。一、动态规划；二、卡特兰公式

解法一：动态规划

1、设 f[i][j]: i表示进栈的个数，j表示“进栈的i个”中出栈的个数。所以 j≤i

举例：
f[1][0]=1：进栈1个元素，出栈0个元素。此时只有1种可能，就是进栈的唯一元素不动。
f[1][1]=1：进栈1个元素，出栈1个元素。此时只有1种可能，就是把进栈的唯一元素直接出栈。
f[2][0]=1：进栈2个元素，出栈0个元素。此时只有1种可能，就是进栈的两个元素都不动。
f[2][1]：进栈2个元素，出栈1个元素。此时有2种可能，第一种是在f[1][1]的情况下第2个元素进栈；第二种可能是在f[2][0]的情况下出栈一个元素
…

2、根据以上推导，可以得到动态转移方程：$f[i][j]=f[i-1][j]+f[i][j-1]（j\le i）$
即 “进栈 i 个，出栈 j 个” 由 两种 状态转移而来：

① 进栈 i-1 个，出栈 j 个（此时再进栈1个就好）；
② 进栈 i 个，出栈 j-1 个（此时再出栈1个就好）

3、初始化：不管进栈几个，出栈为0的，都只有1种可能性，就是都不出
4、注意 j≤i
5、最后要输出的结果就是 f[n][n]，表示进栈n个，出栈n个的可能性
6、注：动态规划的好处是可以求出任意进栈出栈 f[i][j] 的数量。

题解代码：

#include <bits/stdc++.h>
#define ll long long
using namespace std;const int N = 20;ll f[N][N];
// f[i][j]:  i表示进栈的个数，j表示“进栈的i个”中出栈的个数。所以j<=i
// f[i][j] = f[i-1][j] + f[i][j-1]
int main()
{int n;scanf("%d", &n);for(int i = 0; i <= n; i++)  f[i][0] = 1;for(int i = 1; i <= n; i++)for(int j = 1; j <= i; j++)f[i][j] = f[i-1][j] + f[i][j-1];printf("%d", f[n][n]);return 0;
}

解法二：卡特兰数

1、本题可以用卡特兰数来解

卡特兰数（Catalan numbers）是一系列组合数学中出现的自然数，广泛应用于各种计数问题，如二叉树、括号匹配、凸多边形的三角剖分、火车进站出站、有序的01序列等。

卡特兰数的递推公式如下：
$C_n={\sum }_{i=0}^{n-1}{C}_i\cdot C_{n-1-i}$，

其中 $C_0=1$。这一公式表明第n 个卡特兰数等于前 n 个卡特兰数的乘积和。
$C_0=1$
$C_1=C_0\cdot C_0=1$
$C_2=C_0\cdot C_1+C_1\cdot C_0=1+1=2$
$C_3=C_0\cdot C_2+C_1\cdot C_1+C_2\cdot C_0=2+1+2=5$
$C_4=C_0\cdot C_3+C_1\cdot C_2+C_2\cdot C_1+C_3\cdot C_0=5+2+2+5=14$

卡特兰数还可以用以下闭式公式表示：
$C_n=\frac{1}{n+1}\left(\genfrac{}{}{0ex}{}{2n}{n}\right)$ 公式 ①

2、本题因为输入是n，所以是求解第 n 个卡特兰数，故可以直接 公式① 即可。
3、求解公式①时，为了计算$\left(\genfrac{}{}{0ex}{}{2n}{n}\right)$，可以采用组合的递推公式：

$\left(\genfrac{}{}{0ex}{}{n}{m}\right)=\left(\genfrac{}{}{0ex}{}{n-1}{m}\right)+\left(\genfrac{}{}{0ex}{}{n-1}{m-1}\right)$ 公式 ②

公式②的意思是，从 n 个元素中选取 m 个元素的方式，可以通过以下两种方式得到：
1、不选择第 n 个元素：则需要从前 n−1 个元素中选 m 个，这种方式有 $\left(\genfrac{}{}{0ex}{}{n-1}{m}\right)$ 种。
2、选择第 n 个元素：则需要从前 n−1 个元素中选m−1 个，这种方式有$\left(\genfrac{}{}{0ex}{}{n-1}{m-1}\right)$种。
因此，总的选择方式为这两种方式的和。

#include <bits/stdc++.h>
#define ll long long
using namespace std;const int N = 20;ll c[2*N][N];  // c[i][j]:在i个里面挑j个
// c[i][j] = c[i-1][j] + c[i-1][j-1]
int main()
{int n;scanf("%d", &n);for(int i = 0; i <= 2*n; i++)  c[i][0] = 1;for(int i = 1; i <= 2*n; i++)for(int j = 1; j <= i; j++)c[i][j] = c[i-1][j] + c[i-1][j-1];printf("%d\n", c[2*n][n]/(n+1) );return 0;
}

备注：
卡特兰数的应用：
1、括号匹配问题：n对括号中，有多少种合法的匹配方式（由于合法的任意前缀是：左括号的数量不可能小于右括号的数量。故，若记左括号为0，右括号为1，则合法的任意前缀变为：0的数量不可能小于1的数量）
2、出栈次序问题：一个栈的进栈序列为1,2,3…n，有多少种不同的出栈序列（合法的任意前缀是：入栈的数量不可能小于出栈的数量。故，若记入栈为0，出栈为1，则合法的任意前缀变为：0的数量不可能小于1的数量）
3、有序列表问题：给定长度为n的仅包含01的字符串，任意前缀中0的数量不小于1的数量的组合方式有多少种
4、二叉树的计数： 卡特兰数 Cn 表示有 n 个节点的不同二叉树的个数
5、凸多边形的三角剖分：卡特兰数 Cn 表示一个 n+2 边凸多边形可以分成 n 个三角形的不同方式的数量
6、根插入排列：卡特兰数Cn 表示将 n 个元素插入到有根树中的不同方式数量。
7、独特路径问题：卡特兰数 Cn 表示在一个 2n 阶的棋盘上，从左下角到右上角且不穿越对角线的路径数。

解法三、打表法

1、由于本题的 n 不大。故可先用卡特兰数计算每一个n对应的可能性（此时无所谓是否超时）
2、将每一个n对应的结果直接做到数组里。

#include<bits/stdc++.h>
using namespace std;
int main()
{int n, ans[20] = {1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012,742900, 2674440, 9694845, 35357670, 129644790, 477638700};scanf("%d", &n);printf("%d", ans[n]);return 0;
}