Re: [問題] usaco 2-3 Cow Pedigrees (檔名 nocows)
看板Prob_Solve (計算數學 Problem Solving)作者DJWS (...)時間18年前 (2007/02/25 13:56)推噓1(1推 0噓 0→)留言1則, 1人參與討論串4/4 (看更多)
※ 引述《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)
推
02/25 17:49, , 1F
02/25 17:49, 1F
討論串 (同標題文章)
本文引述了以下文章的的內容：
完整討論串 (本文為第 4 之 4 篇)：
Prob_Solve 近期熱門文章
PTT數位生活區 即時熱門文章
