作者misaka0120 (野格炸彈)
看板Grad-ProbAsk
標題[理工] 108交大資演 11
時間Thu Jan 30 12:48:47 2020
http://i.imgur.com/seUdA9O.jpg
http://i.imgur.com/uuUzxGv.jpg
第23題
解答只有D
這題我是用類似matrix chain 的DP做的
但是這樣應該是O(n^3)
這題有n^2內的做法ㄇ
-----
Sent from JPTT on my Sony H9493.
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 101.14.137.229 (臺灣)
※ 文章網址: https://webptt.com/m.aspx?n=bbs/Grad-ProbAsk/M.1580359729.A.777.html
1F：→ zuchang: 你沒辦法證明他的下界 可能存在 只是沒人想到 01/30 12:53
2F：→ zuchang: 就是在有跟沒有之間 沒找到而已 01/30 13:21
3F：推 FRAXIS: matrix chain 有 O(n lg n) 法 01/31 12:01
4F：推 FRAXIS: 這題我猜滿足 quadrangle inequality 所以可以 O(n^2) 01/31 12:09