dp

PROGRAM P1122;

VAR

I:INTEGER;

BEGIN

READ(I);

CASE I OF

1:WRITE('1');

2:WRITE('2');

3:WRITE('5');

4:WRITE('14');

5:WRITE('42');

6:WRITE('132');

7:WRITE('429');

8:WRITE('1430');

9:WRITE('4862');

10:WRITE('16796');

11:WRITE('58786');

12:WRITE('208012');

13:WRITE('742900');

14:WRITE('2674440');

15:WRITE('9694845');

END;

END.

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

int g(int in,int out,int now)

{

if(out==n)return 1;

if(in==0)return g(in,out+1,now-1);

if(now==0)return g(in-1,out,now+1);

return g(in-1,out,now+1)+g(in,out+1,now-1);

} so easy!

cout

动态规划.

设f(i,j,k)表示入栈序中有i个元素、栈内有j个元素，出栈列中有k个元素时最终的出栈序列个数，则：

f(i,j,k)=f(i-1,j+1,k)+f(i,j-1,k+1)

边界：f(0,0,n)=1，i或j等于-1则f(i,j,k)=0

答案就是f(n,0,0)

var n,ans:longint;

procedure dfs(a,b,c:longint);

begin

if c=n then inc(ans)

else

begin

if a>0 then dfs(a-1,b+1,c);

if b>0 then dfs(a,b-1,c+1);

end;

end;

begin

read(n);

ans:=0;

dfs(n,0,0);

writeln(ans);

end.

硬搜居然过了...

怎么会这样？！

编译通过...

├ 测试数据 01：运行超时...

├ 测试数据 02：运行超时...

├ 测试数据 03：运行超时...

├ 测试数据 04：运行超时...

├ 测试数据 05：运行超时...

├ 测试数据 06：运行超时...

├ 测试数据 07：运行超时...

├ 测试数据 08：运行超时...

├ 测试数据 09：运行超时...

├ 测试数据 10：运行超时...

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

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

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

卡特兰数。。。

递归基础题。。。

void f(int top,int tail,int time){

if (time==n+1) {

sum++;

return;

}

if (top!=0) f(top-1,tail+1,time);

f(top+1,tail,time+1);

return;

}

catalan数列

s:=1;

for i:=1 to n do

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

s:=s div (n+1);

write(s);简单啊!

卡特兰数列。。。。。

so easy！！！

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

......

找找规律，交表就行了。不过要注意小数点和初始化！！！

递推递归都可以过~~

出栈次序问题是Catalan数……

设h(0)=1;h(1)=1;

则catalan数满足递归式：

h(n)= h(0)*h(n-1) + h(1)*h(n-2) + ... + h(n-1)h(0) (其中n>=2)

该递推关系的解为：

h(n)=c(2n,n)/(n+1) (n=1,2,3,...)

编译通过...

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

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

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

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

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

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

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

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

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

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

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

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

DP:

f[0]=1(i=1)

f[i]+=f[j]*f;(n>=i>=1 n>=j>=0)

巨快的PUPPY

死搜0MS

最后一个点为208012

我用double 居然208011

通过率..