作者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