返回信息流解题报告：
问题等价于：编号为 1 到 n 的 n 个元素，顺序的进入一个栈，则可能的出栈序列有多少种？
方法：递推+求组合数
令h(1)＝1，满足
h(n)= h(1)*h(n-1) + h(2)*h(n-2) + ... + h(n-1)h(1) (其中n>=2)
该递推关系的解为：h(n)=c(2n,n)/(n+1) (n=1,2,3,...)
同类问题有：
(1)矩阵链乘： P=a1×a2×a3×……×an，依据乘法结合律，不改变其顺序，只用括号表示成对的乘积，试问有几种括号化的方案？
(2)有2n个人排成一行进入剧场。入场费5元。其中只有n个人有一张5元钞票，另外n人只有10元钞票，剧院无其它钞票，问有多少中方法使得只要有10元的人买票，售票处就有5元的钞票找零？(将持5元者到达视作将5元入栈，持10元者到达视作使栈中某5元出栈)
(3)将多边行划分为三角形问题。将一个凸多边形区域分成三角形区域的方法数?
这样的数也叫Calatan数
计算中，对组合数的求解要避免不要超过精度范围
程序：
#include <iostream>
using namespace std;
int C(int a,int b)
{
int i;
int totle=1;
int temp=a;
for(i=1;i<=b;i++)
{
totle=totle*temp/i;
temp--;
}
return totle;
}
int catalan(int n)
{
return C(2*n,n)/(n+1)
}
int main()
{
int test,n;
cin>>test;
while(test--)
{
cin>>n;
cout<<catalan(n)<<endl;
}
}
这是一条镜像帖。来源：北邮人论坛 / acm-icpc / #5137同步于 2007/3/14
该镜像源已超过 30 天没有更新，可能在源站已被删除。
ACM_ICPC机器人发帖
[解题报告]E:冥王星的故事III-和谈
zhao0057
2007/3/14镜像同步0 回复
订阅后，新回复会通过你的通知中心匿名送达。
0 条回复
暂无回复 · 你可以订阅本帖等待新回复。