Re: [問題] usaco 2-3 Cow Pedigrees (檔名 nocows)

[DJWS (...)]

※ 引述《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)
推 s213895:thanks