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

· · 题解

题意

及问你有 n 个数 1 到 n，让你求出栈序列的情况总数。

解法

这个题目是经典的数学题，在这里我们硬求肯定是没有办法的，那么我们不妨以递推的视角看一下。 我们可以设一个数组 f 为在当 n 为一到十八时，可能的序列总数。 那么此时我们的 f_0 和 f_1 只有一种情况，而 f_2 有两种。 那么我们可以先构造一个栈的结构，我们得到了一个输入序列，接下来就要处理了，下一步求递推公式便是本题的精髓，我们的序列是不是从 1 到 n 的，我们的 i 从一开始循环。那么，我们随机挑一个点 k，以 k 为中心点我们的序列被劈成了两半，这两段的情况数为 f_{k-1} 和 f_{i-k} 这两个，那么根据乘法原理，总可能性为 f_{k-1} \times f_{i-k} 。最终公式为 f_n = f_0 \times f_{n-1} + f_1 \times f_{n-2} \cdots + f_{n-1} \times f_0。 那么，我们进行枚举，将 1 到 n 每一个数做这样的处理，将得出的数相乘，就是本题的答案。

代码

#include <bits/stdc++.h>
using namespace std;
int f[55]={1,1,2};
int main(){
    int n;
    cin >> n;
    for(int i=3;i<=n;i++){
        for(int k=1;k<=i;k++){
            f[i]+=f[k-1]*f[i-k];
        }
    }
    cout << f[n];
    return 0;
}