信息学奥赛一本通 1924：【03NOIP普及组】栈

【题目链接】

ybt 1924：【03NOIP普及组】栈

【题目考点】

1. 递推
2. 栈

【解题思路】

• 设数组a，a[i]表示i个数组成的数列经过栈处理后得到的数列总数
• 易知：a[1] = 1。特殊地，将a[0]也设为1。
• 1~n组成数列，要经过栈处理后形成一个数列，要经历以下几个阶段。
  • n入栈
  • r个数字入栈出栈，经过栈处理形成数列2。（0 <= r <= n-1)
  • n出栈
  • l个数字入栈出栈，经过栈处理形成数列1。（0 <= l <= n-1)
• 其中l + r + 1 = n，最后得到的数列为：数列1,n,数列2
• 由l个数字经过栈处理形成数列1，种类数为a[l]，同理，由r个数字组成的数列2的种类数为a[r]。
• 当确定n是数列中的第几个数字，l与r为固定值时，类似"数列1,n,数列2"的数列的种类数为：a[l]*a[r]。
• n若为第1个出栈的数字，n在数列中是第n个数字，此时l为n-1， r为0。n若为第2个出栈的数字，n在数列中是第n-1个数字，此时l为n-2，r为1。将相关量列成表格，有：

n是数列中第几个数字	l	r
n	n-1	0
n-1	n-2	1
…	…	…
2	1	n-2
1	0	n-1

每种数列的种类数为：a[l]*a[r]。已知r = n - 1 - l。
每种数列的种类数加和即为n个数字经过栈处理后得到的数列种类数，其值为:
a [ n ] = ∑ l = 0 n − 1 a [ l ] ∗ a [ n − 1 − l ] a[n] =\sum_{l=0}^{n-1}a[l]*a[n-1-l] a[n]=∑l=0n−1​a[l]∗a[n−1−l]
该公式即为递推公式。

【题解代码】

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