P1044 [NOIP2003 普及组] 栈

题目背景

栈是计算机中经典的数据结构，简单的说，栈就是限制在一端进行插入删除操作的线性表。

栈有两种最重要的操作，即 pop（从栈顶弹出一个元素）和 push（将一个元素进栈）。

栈的重要性不言自明，任何一门数据结构的课程都会介绍栈。宁宁同学在复习栈的基本概念时，想到了一个书上没有讲过的问题，而他自己无法给出答案，所以需要你的帮忙。

题目描述

宁宁考虑的是这样一个问题：一个操作数序列，（图示为 1 到 3 的情况），栈 A 的深度大于 。

现在可以进行两种操作，

1. 将一个数，从操作数序列的头端移到栈的头端（对应数据结构栈的 push 操作）
2. 将一个数，从栈的头端移到输出序列的尾端（对应数据结构栈的 pop 操作）

使用这两种操作，由一个操作数序列就可以得到一系列的输出序列，下图所示为由 ​​1 2 3​​ 生成序列 ​​2 3 1​​ 的过程。

（原始状态如上图所示）

你的程序将对给定的 ，计算并输出由操作数序列  经过操作可能得到的输出序列的总数。

输入格式

输入文件只含一个整数 （）。

输出格式

输出文件只有一行，即可能输出序列的总数目。

输入输出样例

输入 #1复制

3

输出 #1复制

5

说明/提示

【题目来源】

NOIP 2003 普及组第三题

思路分析：

题目要我们求从管倒出来的顺序有多少个，即出栈顺序有多少个，假设三个球123加入栈中，出栈方式可以是123（放进去一个球接着拿出来）、321（三个球全放进去再挨个拿出来）、231（当进去两个球再拿出一个再放第三个再依次拿出来）...。但是由于栈是先进后出的，有些序列比如312就不存在，因为要想先拿出3，1必定在2的后面拿出。

我们假设对于n个元素我们有a[n]个出栈方式，假如第k个元素是最后拿出的，则比k早拿出的元素有k - 1个，比k晚拿出的元素有n - k个，则一共有a[k - 1] * a[n - k]种出栈方式，因为对于早拿出的k - 1个数，其中又存在一个k1是最后那个拿出的，则就有k1 - 1个更早拿出的数，k - 1 - k1个更晚拿出的数，以此类推。我们可以得到，当k取不同的值时，产生的出栈顺序是相互独立的，各自不会产生影响或出栈顺序重复，因为k是不同的。

所以我们将所有k的取值产生的出栈结果加起来，就是我们要求的所有出栈顺序。递推关系式可以写为：a[n] = a[0] * a[n - 1] + a[1] * a[n - 2] + ... + a[n - 1] * a[0]。（表示k取0~n-1时，各自产生的出栈顺序之和）。

另外，对于递推式，要想让其不断执行下去，必须要有一个或多个初始值。本题的初始值是a[0] = 1，因为k==1，表示第1个数最后出栈，比他早出栈的数没有，比他后出栈的有n - 1个数，出栈方式为a[n - 1]，总共出栈方式是a[0] * a[n - 1]，所以a[0] = 1，而不是a[0] = 0，如果a[0] = 0，则总结果变成0，错误；另一个初始值是a[1] = 1，表示第2个数最后出栈，比他早出栈的数只有第一个数，其出栈方式就一种，所以a[1] = 1。

代码如下：

import java.util.Scanner;

public class 栈 {
    static final int N = 20;
    static int[] a = new int[N];
    static int n;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        a[0] = a[1] = 1;
        for(int i = 2; i <= n; i++)
            for(int j = 0; j < i; j++){
                // 递推式：a[i] = a[0] * a[i - 1] + a[1] * a[i - 2] + ... + a[i - 1] * a[0]
                a[i] += a[j] * a[i - j - 1];
            }
        System.out.println(a[n]);
    }
}