P1044 [NOIP2003 普及组] 栈题解

题目

有一个单端封闭的管子，将N(1<=N<=18)个不同的小球按顺序放入管子的一端。在将小球放入管子的过程中也可以将管子最顶上的一个或者多个小球倒出来。请问：倒出来的方法总数有多少种？

输入输出格式

输入格式

输入文件只含一个整数n（1≤n≤18）

输出格式

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

输入输出样例

输入样例

3

输出样例

5

解析

假设i个元素一共有h[i]种出管方式。要求n个元素的出管方式，但是其中每一个元素（从1到n）都可能是最后一个出管的。假设第k个小球是最后一个出管的，比k早入管且早出管有k-1个数，一共有h[k-1]种出管方式；比k晚入管且早出管有n-k个数，一共有h[n-k]种出管方式。这种情况下一共就有h[k-1]*h[n-k]种出管方式。当k取不同值的时候，产生的出管序列也是独立的。所以可以加起来。k的取值范围可以是从1到n。所以递推式是h(n)=h(0)*h(n-1)+h(1)*h(n-2)+……+h(n-1)*h(0),初始条件是h[0]=h[1]=1。

#include<cstdio>
int main(){int n,h[20]={1,1};scanf("%d",&n);for(int i=2;i<=n;i++){for(int j=0;j<i;j++){h[i]+=h[j]*h[i-j-1];}}printf("%d",h[n]);return 0;
}