P1044 [NOIP2003 普及组] 栈题解

本文主要是介绍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;
}

这篇关于P1044 [NOIP2003 普及组] 栈题解的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---