catalan数列???无语.迷惑.

公式是这样的

f(n)=f(1)*f(n-2)+f(2)*f(n-3)+f(3)*f(n-4)+......+f(n-2)*f(1)

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

var a:array[0..20,0..20]of longint;

i,j,m,n:longint;

begin

readln(n); a[1,1]:=1;

for i:=2 to n do

for j:=1 to i do

a:=a+a;

for i:=1 to n do

m:=m+a[n,i];

writeln(m);

end.

呃.....应该就是这样的

n=1:1………………………………=1

n=2:1 1…………………………=2

n=3:1 2 2……………………=5

n=4:1 3 5 5………………=14

n=5:1 4 9 14 14…………=28

n=6:1 5 14 28 42 42……=132

………………

就是这个a:=a+a 嘿嘿

蛮快的哦^_^

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

DP:

由于每个数每次都可能出栈也可能不出栈,那么就可以分为二种情况来看,比如第1个数,它可能是第1个出栈,也可能是第2个出栈……也可能是第n个出栈,那么问题的解就是求f[n],假设1是第i个出栈的,那么它的前面就有i-1个数字,解为f,它的后面就有n-i个数字,解为f[n-i],根据乘法原理,那么解就为:f*f[n-i];i从1到n

CATALAN公式真是简短....

var n,i:longint;

ans:qword;

Begin

readln(n);

ans:=1;

for i:=1 to n do

ans:=ans*(2*n-i+1) div i;

writeln(ans div (n+1));

end.

哈哈~~~

虽然一眼就知道是CATALAN数，但也要写搜索~~要不然浪费这么一个练搜索的机会。

暴力DFS就行

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案错误...　├ 标准行输出

　├ 错误行输出

---|---|---|---|---|---|---|---|-

Unaccepted 有效得分：90 有效耗时：0ms

最后一个点的数据是什么啊

从排列组合的数学知识可以对此类问题加以解决。

我们先对n个元素在出栈前可能的位置进行分析，它们有n个等待进栈的位置，全部进栈后在栈里也占n个位置，也就是说n个元素在出栈前最多可能分布在2*n位置上。

出栈序列其实是从这2n个位置上选择n个位置进行组合，根据组合的原理，从2n个位置选n个，有C(2n,n)个。但是这里不同的是有许多情况是重复的，每次始终有n个连续的空位置，n个连续的空位置在2n个位置里有n+1种，所以重复了n+1次。所以出栈序列的种类数目为：

C(2n,n)/(n+1)=2n*(2n-1)*(2n-2)…*(n+1)/n!/(n+1)=2n*(2n-1)*(2n-2)*…*(n+2)/n!。

本题实际是一个经典的Catalan数模型。有关Catalan数的详细解释请参考《组合数学》等书。

没得说，搜！

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

骗的~~~表鄙视我

哪位大牛介绍下模拟栈的思想？

咱来说个二围的递推式吧 ^_^

f表示尚未入栈的有i个元素,栈内有j个元素,将这种状态变为f[0,0]的方案总数

f=f (i>0,j=0,这种情况下只能入栈)

f=f+f (i>0,j>0,既可入栈,也可出栈)

f=f (i=0,j>0,没有未入栈的元素,只能出栈)

边界条件:f[0,0]=1

目标状态:f[n,0]即所有元素均未入栈变为f[0,0]的方案总数

不妨用dfs+记忆化搜索 这样应该可以减掉很多时间了把

因为这题你无论每次剩的是什么数 只要个数相同 则方案数相同

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

我用的搜索..表BS我...搜索+剪枝似乎只能扛到16,对于原题的18要4S才出解.

基本的思想就是把N个数的进出栈操作看看做N个1和N个的组合数,且对于任意X,有前X项1的个数>=0的个数,则当穷举到不合法的节点就没有必要展开了.

更进一步根据组合数学知识可以证明.所求就是Catalan数列...

我的AC方法：

const catalan:array[1..15]of longint=(1,2,5,14,42,132,429,1430,4862,16796,58767,208012,742900,2674440,9694845);

相当于求n个结点本质不同(左右不一样)的二叉树的个数

对于每个元素,总要出栈,关键是在哪个元素后出栈

构造一颗二叉树,其中序遍历为出栈序列

于是问题得到转化

求n个结点本质不同(左右不一样)的二叉树的个数

1.dp

2.C(n,2n)/(n+1)

dp的公式是

f[0]:=1;

f[i]= sum(f*[k]) (0

什么是CATALAN数列

有没有哪位大牛介绍一下CATALAN数列..

此题就是Catalan 数列，公式是 (1/(n+1))*((2n*(2n-1)*(2n-2)...(2n-n+1))/(n*(n-1)*(n-2)...3*2*1)).

这题目应该普通方法做可以了。

谁有好点的搜索方法,CATALAN数列数学性太强,高手请指教