M04077: 出栈序列统计

dp, dfs, math, http://cs101.openjudge.cn/practice/04077/

【黄宇曦地球与空间科学学院】思路：直接思考 dp。考虑第一个在什么时候被弹出不难发现转移方程。事实上这也是所谓的 Catalan 数。

cpp

#include <bits/stdc++.h>

using namespace std;

#define all(x) begin(x), end(x)
#define sz(x) (int) (x).size()

using i64 = long long;
using u64 = unsigned long long;
using i128 = __int128_t;
using u128 = __uint128_t;
using pii = pair<int, int>;
using vi = vector<int>;
using usi = unordered_set<int>;

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    int n;
    cin >> n;
    vi dp(n + 1, 0);
    dp[0] = dp[1] = 1;
    for (int i = 2; i <= n; i++) {
        for (int j = 0; j < i; j++) {
            dp[i] += dp[j] * dp[i - 1 - j];
        }
    }
    cout << dp[n] << '\n';
    return 0;
}

【张真铭元培】思路：Catalan数 $𝐶_{𝑛}$ 的递推关系有着天然的递归结构：规模为 $𝑛$ 的计数问题 $𝐶_{𝑛}$ ，可以通过枚举分界点，分拆为两个规模分别为 $𝑖$ 和 $(𝑛 - 1 - 𝑖)$ 的子问题。这一递推关系使得Catalan数广泛出现于各类具有类似递归结构的问题中。

路径计数问题：有一个大小为 $n \times n$ 的方格图，左下角为 $(0, 0) (0, 0)$ ，右上角为 $(𝑛, 𝑛) (n, n)$ 。从左下角开始，每次都只能向右或者向上走一单位，不走到对角线 $y = x$ 上方（但可以触碰）的情况下，到达右上角的路径总数为 $C_{n}$ 。

圆内不相交弦计数问题：圆上有 $2 n$ 个点，将这些点成对连接起来且使得所得到的 $n$ 条线段两两不交的方案数是 $C_{n}$ 。

三角剖分计数问题：对角线不相交的情况下，将一个凸 $(n + 2)$ 边形区域分成三角形区域的方法数为 $C_{n}$ 。

二叉树计数问题：含有 $n$ 个结点的形态不同的二叉树数目为 $C_{n}$ 。等价地，含有 $n$ 个非叶结点的形态不同的满二叉树数目为 $C_{n}$ 。

括号序列计数问题：由 $n$ 对括号构成的合法括号序列数为 $C_{n}$ 。

出栈序列计数问题：一个栈（无穷大）的进栈序列为 $1, 2, 3, \dots, n$ ，合法出栈序列的数目为 $C_{n}$ 。

数列计数问题：由 $n$ 个 $+ 1$ 和 $n$ 个 $- 1$ 组成的数列 $a_{1}, a_{2}, \dots, a_{2 n}$ 中，部分和满足 $a_{1} + a_{2} + \dots + a_{k} \geq 0 (k = 1, 2, 3, \dots, 2 n)$ 的数列数目为 $C_{n}$ 。

$C_{n} = \frac{(4 n - 2)}{n + 1} C_{n - 1}, n > 0, C_{0} = 1.$

代码：

cpp

#include <iostream>

auto main() -> int {
  std::cin.tie(nullptr)->sync_with_stdio(false);

  int n;
  std::cin >> n;
  int c_prev = 1;
  int c_curr = 1;
  for (int i = 1; i <= n; ++i) {
    c_prev = c_curr;
    c_curr = (4 * i - 2) * c_prev / (i + 1);
  }
  std::cout << c_curr << '\n';
}

M04077: 出栈序列统计 ​

M04077: 出栈序列统计