P1044 [NOIP 2003 普及组] 栈

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

int main() {
    int n;
    cin >> n;

    // 直观理解：一个输出序列的第一个元素是 k，说明 1..k-1 全都进过栈并压在 k 下面，
    // 也就是 k 是最先被弹出（输出）的数。输出序列因此被 k 劈成两段：
    // 左边 k-1 个数、右边 n-k 个数，两段互不影响，方案数相乘。
    // 所以 f[n] = sum_{k=1}^{n} f[k-1] * f[n-k]，也就是第 n 个卡特兰数。
    vector<long long> f(n + 1, 0);
    f[0] = 1;                        // 空序列算 1 种

    for (int i = 1; i <= n; i++) {
        for (int j = 0; j < i; j++) {
            f[i] += f[j] * f[i - 1 - j];   // 左边 j 个、右边 i-1-j 个
        }
    }

    cout << f[n] << "\n";
    return 0;
}