作者DJWS (...)
看板Prob_Solve
标题Re: [问题] usaco 2-3 Cow Pedigrees (档名 nocows)
时间Sun Feb 25 13:56:52 2007
※ 引述《s213895 (鬼才)》之铭言：
: 很明显的
: long solve(){
: for(long k=1;k<=K;++k){
: s[1][k]=1;
: for(long n=2;n<=N;++n){
: s[n][k]=0;
: for(long l=1;l<=n-2;++l){
s[n][k]+=s[l][k-1]*s[n-1-l][k-1];
: s[n][k]%=9901;
: }
: }
: }
: }
黄色部份就是递回公式罗
跟catalan number的递回解相当接近
懂了catalan number的求法之後
这个问题也就不难理解了
演算法/资料结构的书籍
大致上都会提到catalan number的计算方法
这应该算是个经典问题吧
你可以参考演算法/资料结构的书籍
或者上网找找catalan number的资料
应该就能找到你想知道的东西了～
PS: 我想书上通常会把 catalan number 和 binary tree 放在一起的～
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 140.112.90.80
※ 编辑: DJWS 来自: 140.112.90.80 (02/25 13:58)
1F：推 s213895:thanks 02/25 17:49