Re: [理工] 107台大資演對答案
※ 引述《qscez (天使在身旁 xD)》之銘言：
: V.
: (a)
: (2)
這題應該是用 DP 解，以下是遞迴關係：
令 F(l, r) 表示從左側取 l 個和從右側取 r 個時最大 alternative sum。
F(l, r) = max(F(l-1, r) + a_l, F(l, r-1) + a_{n - r + 1}) if l+r 是奇數
max(F(l-1, r) - a_l, F(l, r-1) - a_{n - r + 1}) if l+r 是偶數
: VI.
: (a) 對Va.Vb 做 Dijkastra Time:O(VlogV+E)
這問題其實是在 G 上找 minimax path，也就是找 Va 到 Vb 的 path 中，
path 上最大 weight 的邊最小的 path，詳細介紹可以看 wiki。
https://en.wikipedia.org/wiki/Widest_path_problem
Linear time 的解法也寫在 wiki 上了
https://en.wikipedia.org/wiki/Widest_path_problem#Undirected_graphs
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 73.202.90.47
※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1549235991.A.2DB.html
討論串 (同標題文章)
完整討論串 (本文為第 2 之 4 篇)：
理工
6
26