首先,我们设f(n)=序列个数为n的出栈序列种数。(我们假定,最后出栈的元素为k,显然,k取不同值时的情况是相互独立的,也就是求出每种k最后出栈的情况数后可用加法原则,由于k最后出栈,因此,在k入栈之前,比k小的值均出栈,此处情况有f(k-1)种,而之后比k大的值入栈,且都在k之前出栈,因此有f(n-k)种方式,由于比k小和比k大的值入栈出栈情况是相互独立的,此处可用乘法原则,f(n-k)*f(k-1)种,求和便是Catalan递归式。看到大家的题解都写到了卡特兰数,但是没有细细的讲讲这跟本题有什么关系本题的描述十分简单。n个数依次进栈,可随机出栈。求有几种可能。
dfs可以解,但是递推仿佛好像如同看上去貌似更简单一些。
1. 比x小 2. 比x大
比x小的数有x-1个,所以这些数的全部出栈可能为f[x-1]
比x大的数有n-x个,所以这些数的全部出栈可能为f[n-x]
这两部分互相影响,所以一个x的取值能够得到的所有可能性为f[x-1] * f[n-x]
另外,由于x有n个取值,所以
ans = f[0] * f[n-1] + f[1] * f[n-2] + … + f[n-1] * f[0];
这,就是传说中的卡特兰数附上代码:
int n, f[30];
int main()
{
//递推实现卡特兰数
scanf("%d", &n);
f[0] = 1, f[1] = 1;
for(int i=2; i<=n; i++)
for(int j=0; j<i; j++)
f[i] += f[j] * f[i-j-1]; //递推公式 //f(2)=f(0)*f(1)+f(1)*f(0);
printf("%d", f[n]);
return 0;
}
卡特兰数
这是一道经典的卡特兰数例题
卡特兰数有四个公式,显然这题数据太水都可过,但我们要分析每个公式的用处。
以下内容神犇请无视(话说神犇也不会看这种水题的题解)
公式一
递归公式
h(0)=h(1)=1
h(n)= h(0) * h(n-1)+h(1) * h(n-2) + … + h(n-1) * h(0) (n>=2)
如果我们用这个公式显然我们要使用递归算法,那么数据一大就在时空上很麻烦
公式二
递推公式
h(n) = h(n-1) * (4 * n-2) / (n+1)
这个公式应用递推,看上起十分和善
但对大数据呢?
我们注意到大数据的时候h(n)会很大,这时候题目一般会让你对某素数取模(当然你可以打高精度(划掉))
但你在取模过程中难保一个 h(n) % mod = 0
那么根据公式下面所有的数都会等于0,于是你就愉快的WA了
公式三
组合数公式1
h(n) = C(2n,n) / (n+1) (n=0,1,2,…)
卡特兰数可以与组合数联系起来,得到上面的公式
而组合数就是一个杨辉三角,可以递推得到(这个不属于这道题的讨论范围我假装你们都会(逃))
但我们发现对于大数据你要取模,而对于除法你是没办法用膜的性质的(当然你可以应用逆元(划掉)),所以造成了麻烦
公式四
组合数公式2
h(n) = c(2n,n) – c(2n,n-1) (n=0,1,2,…)
与组合数公式1不同这个是两个组合数的减法
减法是可以用膜的性质的,于是你可以愉快的AC了。
所以我写了这么多就是想说,对于一个特定的任务,可能会有很多方法求解,但其实只要稍稍分析一下就会发现有一种方法是通用而优美的,我在没认真思考前都是记的四个公式,但是有一天我真的认真想过后才发现其实我就记住公式四就好了。
所以学习啊,还是要学会认真思(tou)考(lan):
using namespace std;
int n;
int c[siz*2][siz];
int main()
{
scanf("%d",&n);
for(int i=1;i<=2*n;i++) c[i][1]=c[i][i]=1;
for(int i=3;i<=2*n;i++)
for(int j=2;j<i;j++)
c[i][j]=c[i-1][j]+c[i-1][j-1];
printf("%d",c[2*n][n]-c[2*n][n-1]);
return 0;
}