TYVJ P2830 出栈序列统计

描述

栈是常用的一种数据结构,有n令元素在栈顶端一侧等待进栈,栈顶端另一侧是出栈序列。你已经知道栈的操作有两•种:push和pop,前者是将一个元素进栈,后者是将栈顶元素弹出。现在要使用这两种操作,由一个操作序列可以得到一系列的输出序列。请你编程求出对于给定的n,计算并输出由操作数序列1,2,…,n,经过一系列操作可能得到的输出序列总数。

输入格式

一个整数n(1

输出格式

一个整数,即可能输出序列的总数目。

测试样例1

输入

3
输出

5

卡特兰数。。。。不要被火车进栈问题的水水版骗了。。。。写了半天才发现需要高精度

#include<iostream>
using namespace std;
unsigned long long fn[110];
unsigned long long f(int n){
	if(fn[n]!=0)return fn[n];
	if(n<1) return 1;
	unsigned long long now=0;
	for(int k=1;k<=n;k++)
	now += f(k-1) * f(n-k);
	return fn[n]=now;
}
int main()
{
	int n;
	cin>>n;
	cout<<f(n);

}

 

此条目发表在TYVJ, 卡特兰数, 排列组合分类目录。将固定链接加入收藏夹。