※ 引述《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://webptt.com/cn.aspx?n=bbs/Grad-ProbAsk/M.1549235991.A.2DB.html