题解：P1044 [NOIP 2003 普及组] 栈

M1__ · 2025-03-22 16:31:57 · 题解

题解：P1044 [NOIP 2003 普及组] 栈

• Link | Blog
• 直接按照卡特兰数做即可，但是考虑证明。

  前置知识

• 卡特兰数：组合数学中一种常出现于各种计数问题中的数列。它的前几项为： C(0)=1,C(1)=1,C(2)=2,C(3)=5,C(4)=14,C(5)=42

  题目思路

• 不妨设第一个入栈的元素是第 k 个出栈的元素，则前面的元素 1 \sim k-1 必须在 k 前完成出入栈。则方案数为 C(k-1)；
• 则后面的数 k \sim n 有 C(n-k) 种方案。总的方案数为 C(k-1) \cdot C(n-k)。
• 可以把样例代入证明：
  • 当 k=1 时，有 C(0) \cdot C(2)=2；
  • 当 k=2 时，有 C(1) \cdot C(1)=1；
  • 当 k=3 时，有 C(2) \cdot C(0)=2；
  • 因此总方案为 2+1+2=5。
• 综上，答案为： C(n)=\sum _{k=1}^{n} C(k−1) \cdot C(n−k)
• 将其化为： C(n)=\frac{2(2n−1)}{n+1} \cdot C(n−1)

  于是我们可以推出卡特兰数列的前 18 项，然后根据 n 输出即可。

  代码实现

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=100;
ll n,sum[N];
int main() {
    cin>>n;
    sum[1]=1;
    for(int i=2;i<=18;i++){
        sum[i]=sum[i-1]*2*(2*i-1)/(i+1);
        //cout<<sum[i]<<"\n";
    }
    cout<<sum[n];
    return 0;
}