Re: [理工] [algo] 100台大資工 軟體設計

[mqazz1 (無法顯示)]

※ 引述《lexa (    )》之銘言：
: 題目在此
: http://exam.lib.ntu.edu.tw/sites/default/files/exam/graduate/100/100418.pdf
: 我想先問第4題
: 好像沒有dummy key 這該怎麼算呢?

借連結問一下

請問第4題的(a)

他OBST的cost的那個遞迴式要怎麼寫呢?

謝謝

--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.118.110.186
推 pikachu123:F(Ki)~F(Kj)總和+min(i<=k<=j){ci.k-1,ck+1.j}
→ pikachu123:上面那個是4B 4A就 填0
→ pikachu123:                                   打錯這裡是相加
請問pi大的4B是這樣填嗎?
[  j      ]
[ Σ F(Kp)] +  min  { C(i,r-1) + C(r+1,j) }
[p=i      ]  i<=r<=j
推 pikachu123:話說回來這題7個點會算到死....
恩 算到一半就不想算了..花很多時間才10分(搞不好粗心就錯了)
不知pi大有沒有什麼"比較好"的暴力法去解這題= =?
推 pikachu123:4B就那樣填 大概還是要填表格去做 反正又台大又沒說要
→ pikachu123:讓你做完XD
→ pikachu123:7個點暴力法也不太好try
謝謝
自從隨機老師不教演算法之後
很理論證明的題目就比較少了= =
反而DP這種花時間trace的題目就變多了..
※ 編輯: mqazz1          來自: 140.118.110.186      (12/31 21:29)
推 harrypotter2:推皮卡丘大，跨年夜辛苦啦~~
推 Byzantin:很討厭這種題目~"~ 容易忘記又容易出錯又很花時間