Question

请帮我看一下这个pascal程序哪里错了

题目：
【问题背景】栈是计算机中经典的数据结构，简单的说，栈就是限制在一端进行插入删除操作的线性表。
栈有两种最重要的操作，即pop（从栈顶弹出一个元素）和push（将一个元素进栈）。
栈的重要性不言自明，任何一门数据结构的课程都会介绍栈。宁宁同学在复习栈的基本概念时，想到了一个书上没有讲过的问题，而他自己无法给出答案，所以需要你的帮忙。

【问题描述】

宁宁考虑的是这样一个问题：一个操作数序列，从1，2，一直到n（图示为1到3的情况），栈A的深度大于n。
现在可以进行两种操作，
1.将一个数，从操作数序列的头端移到栈的头端（对应数据结构栈的push操作）
2. 将一个数，从栈的头端移到输出序列的尾端（对应数据结构栈的pop操作）
使用这两种操作，由一个操作数序列就可以得到一系列的输出序列，下图所示为由1 2 3生成序列2 3 1的过程。（原始状态如上图所示）

你的程序将对给定的n，计算并输出由操作数序列1，2，…，n经过操作可能得到的输出序列的总数。

程序：01.program p1;
02.var
03. total:longint;
04. n:longint;
05.
06.procedure solve(l,m,r:longint);
07. begin
08. if l<>0 then solve(l-1,m+1,r);
09. if m<>0 then solve(l,m-1,r+1);
10. if r=n then inc(total);
11. end;
12.
13.begin
14. read(n);
15. total:=0;
16. solve(n,0,0);
17. writeln(total);
18.end.

运行结果：
得分： 60分
有效耗时： 2141毫秒
测试结果1: 通过本测试点|有效耗时188ms
测试结果2: 通过本测试点|有效耗时156ms
测试结果3: 通过本测试点|有效耗时203ms
测试结果4: 通过本测试点|有效耗时719ms
测试结果5: 选手程序运行超过时限
测试结果6: 输出过长|用户输出数据超过标准输出两倍[标准输出1位|选手输出7位]
测试结果7: 输出过长|用户输出数据超过标准输出两倍[标准输出1位|选手输出7位]
测试结果8: 通过本测试点|有效耗时172ms
测试结果9: 通过本测试点|有效耗时703ms
测试结果10: 选手程序运行超过时限

Answer 1

能过6个点从正确性上应该没有问题
由于你写的程序是一个一个加的，如果答案非常大的话累加次数也会非常大
如果最后答案为10^9的话你至少累加了10^9次，这无疑是超时的
很显然一个一个加明显是效率最低的，于是我们试图要找到一个方案可以一次性加上多个

方案1：动态规划
1‘状态确立：我们令f[i,j]表示当剩下i个元素没有进栈，在栈中剩余j个元素时，可能得到的输出序列的总数
比如当栈中有1个元素，没有进栈的有1个元素，可能序列就有2种，即f[1,1]=2
通过这个我们很容易得到初始结论：f[0,i]=1 无论i是多少
也就是说所有元素已经进栈，在栈中还剩下i个元素时，只能得到一种输出序列
由这个状态我们得到，最后我们需要求出f[n,0]
即有n个元素没进栈，栈里没有元素时可能的输出序列

2’状态转移：接着我们要通过递推求出f[n,0]
我们有2中操作，第一种是从栈中去掉1个元素，第二种是从未入栈的元素中放一个进栈
我们需要把这2中情况可能的值加起来
对于一个f[i,j]进行第一种操作之后变成f[i,j-1],第二种操作变成f[i-1,j+1]
将这2种情况加起来
于是f[i,j]=f[i,j-1]+f[i-1,j+1]
前提是i<>0 j<>0
当j=0的时候，栈中没有元素，只能进行进栈操作,不需要加入第二种操作的情况
所以f[i,0]=f[i-1,1]
当i=0时之前说过，f[0,j]=1

接着可以写程序了
program p1;
var f:array[0..30,0..30]of qword;
i,j,n:longint;
begin
readln(n);
for i:=1 to n do
f[0,i]:=1;
for i:=1 to n do
for j:=0 to n do
begin
if j=0 then
f[i,j]:=f[i-1,j+1]
else
f[i,j]:=f[i-1,j+1]+f[i,j-1];
end;
writeln(f[n,0]);
end.

方案2：直接计算第n项卡特兰数
PS：本人才疏学浅，数学推导也不会，只能直接给程序了
卡特兰数第n项为 C(2n,n)/(n+1) C(2n,n)就是2n取n的组合
程序：
program p1;
var n,i:longint;
x:double;
begin
readln(n);
x:=1;
for i:=1 to n do
x:=x*(n+i)/i;
x:=x/(n+1);
writeln(round(x));
end.

Answer 2

你这爆搜啥剪枝也没有不超时才怪。。。

Answer 3

这个程序应该是最省的了，应该是数据有问题，要改进的话只能别用过程