作者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/cn.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